数据结构课程老师布置的作业……昨天已经截止……于是今天拿来问问大家……
【题目描述】
Shrek 在他生活的大沼泽里做小本生意。他每天骑着小驴Donkey 到大沼泽里的n 个小岛去卖货。
这n 个小岛由n‐1 座长度相等的桥相连，而且各岛之间都因此相互通达。
Shrek 每天早上从家出发，而且在路上不走回头路，也就是说同一天内他不可能经过同一岛或同
一桥两次或更多。到达某一岛后，他先卖一会儿货，然后随机选择并前往一个当天尚未去过的岛；如
果己无路可走，他就干脆停下来休息以打发掉当日剩余的时光，然后于次日再从该岛出发继续卖货。
问题是Donkey 的胃口太大。每经过一座桥，它都要吃掉一整包（体积为1 个单位）的草料。为
此，Shrek 要准备一个足够大的背包来装草料。当然，他特别想知道，究竟需要准备多大的背包，才
能保证自己永远不会因为这头馋嘴巴的懒驴，而在明明还有路可走的情况下却不得不停下来。
现在，请你通过编程帮助Shrek 算算，他到底需要一个多大的背包。
【输入】
第一行是正整数n，表示岛的总数，各岛从1 到n 编号。
接下来的n‐1 行各有以空格分隔的两个整数，表示由一座桥联通的两个岛（的编号）。
【输出】
仅有一行，含一个整数，即Shrek 所需背包的最小体积。

我的想法是，构造一个多叉树，每个结点表示一个城镇，有父亲节点和长子结点，以及哥哥、弟弟结点。
每个结点的直系孩子，表示这个和这个城镇直接相连的那些城镇，并且不包括父亲（虽然父亲结点的城镇也和本结点直接相连）。

然后就构造树，每次插入数据，都找当前的树上有没有要插入的数据，如果都没有，那就在将一个数据插入到根节点的直系孩子中，另一个结点作为这个结点的孩子插入。
如果仅有一个存在于树上，那就将另一个结点插入这个结点的直接孩子，作为长子。
如果两个孩子都在树上，那么肯定是根节点的不同的子树上，合并这两个树。

输入完成，就构造完成了这个树。
然后找最远点，然后用最远点找与它距离最远的点。输出距离。

请问这个题这么设计算法可以吗？如果可以，要怎么改进？
网上测试的时候总是有一个点超时。

新人第一次来，忽然发现还有“结贴”这个东东，论坛好神奇啊……

可以对这道题建立“无向图”模型。。在其上执行深度优先搜索，搜索出的联通分量中的结点个数 就是最长路 。

您的宏观上的意思，我好像有些明白了。
首先建立无向图；
然后开始深度优先遍历：
    第一次从小岛1开始深度优先遍历，求得一条最长路径；
    第二次从小岛2开始深度优先遍历，又求得一条最长路径；
    ……
最后从这n条路径中选择最长的，是这样吗？

[ 本帖最后由 leizisdu 于 2011-11-22 10:32 编辑 ]

恩，是这意思。
深搜出所有的路，选择其中最长的

哦，好的