树的动态规划及构造.doc

【关键字】 树的动态规划 上方子树 树的构造【摘要】 本文通过几道关于树的题目，分析了树的动态规划与构造这两种类型题目的解法。【目录】一、树的动态规划2例1Centroid2例2Computer Network3例3数据生成器5例47小结 7二、树的构造8例58例6树重建 (Rebuild)9例7毛毛虫 (Caterpillar)10三、总结 12【正文】 树，是一种很特殊的数据结构，关于它的题目十分的多，几乎在大部分的比赛当中都会出现这类型的题目，而且研究树的题目也是十分有趣的。由于以树为背景，题目会很明显地渗透了树的特征，而树的特征也正是我们解决这类问题的突破口。 树的问题往往会有一个十分突出的特点：数据量十分大。由于树是十分特殊的图：连通图，n个顶点，n-1条边。因此在空间可以承受的范围内n可以达到很大。而且树的特殊结构也决定了算法的优越性。正因为树的特殊，通常能够找到十分高效的算法（比如说是O(n)）。于是我们解决这类题目的时候应当牢牢抓住树的特征，认真分析问题，这样就能比较好地解决题目了。 下面举一些例子谈谈树的动态规划与构造。一、树的动态规划 树的动态规划，顾名思义，就是在树上面进行动态规划。树的动态规划很有特点，虽说对某个结点来说，状态转移的复杂度是不确定的（这取决于与它相连的边数），但是总体来说，每条边通常只会对应常数次状态转移，所以总的复杂度是O(n)的，这就使树的动态规划十分高效。 例如下面这道题目：例1CentroidYou are given an undirected connected graph, with N vertices and N-1 edges (a tree). You must find the centroid(s) of the tree. In order to define the centroid, some integer value will be assosciated to every vertex. Lets consider the vertex k. If we remove the vertex k from the tree (along with its adjacent edges), the remaining graph will have only N-1 vertices and may be composed of more than one connected components. Each of these components is (obviously) a tree. The value associated to vertex k is the largest number of vertices contained by some connected component in the remaining graph, after the removal of vertex k. All the vertices for which the associated value is minimum are considered centroids.InputThe first line of the input contains the integer number N (1=N=16 000). The next N-1 lines will contain two integers, a and b, separated by blanks, meaning that there exists an edge between vertex a and vertex b.OutputYou should print two lines. The first line should contain the minimum value associated to the centroid(s) and the number of centroids. The second line should contain the list of vertices which are centroids, sorted in ascending order.Sample Input71 22 32 41 55 66 7Sample Output3 11 题目的意思是说：给出一棵具有N个结点的树(1=N=16 000)，找出这棵树的“质心”。“质心”的定义如下：对于树中的每个结点K。若将它删去，则一棵树会变为若干棵树，取这些树的结点数中最多的作为结点K的值，若K为树的质心，则结点K的值是所有结点的值中最小的。要你求出树的所有质心。 这是一道关于树的题目。我们要找的其实就是一个结点K，使它所有子树的结点数的最大值最小。我们只需对每一个结点都求出它的每棵子树的结点数，就能求出树的所有质心了。求一棵子树的结点数可以用动态规划来解决。由于题目输入的是一棵无根树，我们可以先随便找一个结点作为根节点，然后对这棵树遍历。用F(A)表示以结点A为根的树的结点个数。则 ，其中Son(A)表示结点A的儿子集合。还有一个细节是必须解决的。如右图，题目输入的是一棵无根树，我们把它转成了有根树，例如结点A是结点K的父亲。其实在原来的树中，从结点A连出去的一棵树也算是K的一棵子树，不妨称这棵子树为“K的上方子树”，因此我们也必须把结点K的“上方子树”的结点数也求出来。而求的方法是很简单的，只需用总结点数减去K这个子树的结点数就行了。这样我们就在O(n)的时间内用动态规划解决了这个问题。（程序请参见附录）下面再看一道例题：例2Computer NetworkA school bought the first computer some time ago. During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know for each computer number Si - maximum distance, for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.InputThere is natural number N (N=10000) in the first line of input, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 109. Numbers in lines of input are separated by a space.OutputWrite N lines in output file. i-th line must contain number Si for i-th computer (1=i=N).Sample test(s)Input31 11 2Output233 题目的意思是说：一间学校前几年时间买进了第一台电脑。这几年又陆续买了N-1台电脑。后面买的电脑都与先前买的某一台电脑用网线连接起来。现在我们知道后面的N-1台电脑分别与哪台电脑连接以及相应的网线的长度，任务是对每一台电脑K都求出，在另外的N-1台电脑中，离K最远的那台电脑与K的距离（即它们之间的网线的总长度）。这也是一道关于树的题目，而且和例1十分相似，也是符合动态规划的要求的。我们也可以类似地先任意选择一个结点作为树的根把树转为有根树，然后用动态规划对每个结点K都求出以结点K为根的子树的深度。然而我们同样碰到了上面的问题，就是K的父亲A也会连出去一棵树，它在原来的无根树中同样也属于K的子树（即K的“上方子树”）。但是，现在我们要求的是树的深度，就不像上题求结点数那样这么容易求了。如果我们仍然用动态规划，从A的子树（除去K这一棵）中选出深度最深的，然后将它的深度加上AK的长作为“上方子树”的深度，就有可能出现下面这种情况：对于A的每一个儿子K，都要求K的“上方子树”，而每一次我们都必须求A的所有子树（除去K的那一棵）中深度最大的那一棵。这样的话时间复杂度就变为O(n2)了，显然是十分不优的。为了解决这个问题，我们在前面那个过程中，求A的所有子树的深度的时候，可以顺便求出A的子树中深度最大的两棵，并记录是哪两棵。在以后求K的“上方子树”时，就能判断一下，K是不是它父亲A的最深的子树。如果不是，那么A的最深的子树的深度加上AK的长度就是K的“上方子树”的深度；否则A的第二深的子树的深度加上AK的长度就是K的“上方子树”的深度。这样就能够用O(n)的复杂度求出所有结点的“上方子树”的深度了。 解决了这些问题后我们就能直接进行输出了。（程序请参见附录）在2003年的全国赛中也有一道十分类似的题目：例3数据生成器【题目背景】小明在做NOI2003练习赛的幸福的老鼠时觉得题目太简单了，于是对原题做了一些扩展：将原题的N从20扩展到200000。l将原题经过一条街道需要的时间改为Ti（1 Ti 1000000000）分钟（i为街道的编号）。l增加了一个条件：小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离。l即使这样，他仍然很快地做了出来。于是，小明打算做一些输入文件来测试他的程序。现在他已经生成了一些符合题意的图，不过为了增大测试数据的难度，他希望你能帮他选取一组X、Y、Z，使老鼠拿到礼物的时间尽可能地大。【小明扩展的题目（注意，你并不需要解决此题）】幸福的老鼠Jerry要过生日了，小狗大狗分别送了它一份生日礼物。现在Jerry打算从自己家X出发，先到小狗家Y（因为小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离），再到大狗家Z，将两份礼物取回。卡通城由N（3 N 200000）个居住点和N-1条连接居住点的双向街道组成，经过第i条街道需花费Ti（1 Ti 1000000000）分钟的时间。可以保证，任两个居住点间都存在通路。不妨设Jerry家在点X，小狗家在点Y，大狗家在点Z。现在，请你计算，Jerry最快需要耗费多长时间才能拿到生日礼物？【任务描述】定义：令|AB|表示卡通城中从A点走到B点需要的最少时间。给出卡通城的地图，找到一组X、Y、Z，使得：|XY|XZ|l|XY|+|YZ|最大。l并求出此时|XY|+|YZ|的值。【输入文件】输入文件jerrygen.in第一行是两个整数N（3 N 200000）和M（M=N-1），分别表示居住点总数和街道总数。从第2行开始到第N行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1Ui, Vi N，1 Ti 1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。【输出文件】输出文件jerrygen.out仅包含一个整数T，即|XY|+|YZ|的最大值。【样例输入】4 31 2 12 3 13 4 1【样例输出】4 这是一道树的题目，而且数据量十分大(3 N 200000)。这道题并不能一眼就看出用动态规划解决，但仔细分析一下还是不难找到它的算法的。 为什么会想到动态规划呢？题目要我们求|XY|+|YZ|的最大值。我们先从X走到Y，再由Y走到Z，首先可以肯定的是这两条路是必定有交点的。（至少Y就已经是一个交点了。）不妨设这些交点中离X最近的交点为O。那么我们等于从X走到O，再从O走到Y，然后从Y走回O，再从O走到Z。所以路程就是S=|OX|+|OZ|+2|OY|。如果我们对树中的每一个结点O，找出它的子树中三棵最深的子树，并设三棵最深的子树中离O最远的点分别为A,B,C。由于路程S中，|OY|的系数是2，其余两个都是1，因此我们应当让|OY|尽可能大。然而题目有个条件说|XY|XZ|，即|OX|+|OY|OX|+|OZ|，|OY|OZ|。所以我们应当让A,B,C中离O最远的点作为Z，第二远的点作为Y，最近的点作为X。这样|OX|+|OZ|+2|OY|就是以O为“中转点”时最长的路程S。 现在问题转化为如何高效地求出树中的每一个结点O的所有子树的深度。这是一个我们十分熟悉的模型动态规划！ 求每个结点所有子树的深度在例2中已经分析得比较详细了，但鉴于这道题目的数据量十分大，我们可以在细节上对代码做一些优化，尽量减少程序运行的时间。例如我们在存储一棵树的时候可以用数组来模拟指针的操作，在读文件的时候可以使用缓存，在递归的过程中尽量减少变量的使用，以减少使用空间太大而影响了程序的运行速度等等。具体的实现方法请参照附录中的程序注释。 接下来也是一道关于树的动态规划的题目：例4给出一个有n个结点的树，每个结点i上有一个正权w(i)，每条边也有一个正权c(j)，设计一个线性时间复杂度的算法，找出一个结点u，使得对于所有其他点i，w(i)L(i)的总和尽量小。其中L(i)表示i到u的路程（即路径上所有边的权和）。输入文件第一行为结点个数n。接下来的n行中，第i行为w(i)。接下来的n-1行每行3个整数k1,k2,c表示结点k1,k2之间有一条边，边的权为c。输出文件第一行应为结点u。第二行输出w(i)L(i)的总和。 分析：这题与前两道例题的本质是一样的，都属于树的动态规划类题目，只是形式上变了一下。我们仍然可以先随便找一个结点作为根结点，使树变为有根树。然后就能进行动态规划了。我们用Sum(k)表示以结点k为根的子树的所有结点的权值之和，即 ，其中Tree(k)表示以k为根的子树。再用Value(k)表示以结点k为根的子树的所有结点的w(i)L(i)之和，即 。则有如下动态规划方程： ，其中Son(k)是k的儿子集合，c(k,i)是k,i之间的边的权。这样我们就能用动态规划在O(n)的时间内求出所有结点的Value值。 但是Value(k)并不是题目中所说的“对于所有其他点i，w(i)L(i)的总和”，因为从k的父亲A连出去的那棵子树（即k的“上方子树”）中的结点还没有计算。因此我们要对Value(k)的值进行更正，即应将Value(k)的值加上k的“上方子树”中的结点i的w(i)L(i)。这个可以在O(1)的时间内求出，式子如下： ，其中A为k的父亲，Total表示所有结点的权值之和，c(A,k)表示A,k之间的边的权值。由于A是k的父亲，所以我们递归到k的时候，Value(A)的值是已经更新过的，因此式子中的 表示k的“上方子树” （以A为根结点）的Value值，然后 表示k的“上方子树”中的结点i从“到A的距离”变为“到k的距离”，w(i)L(i)所增加的量。因为k的“上方子树”中的任意一个结点i，i与k的距离是比i与A的距离要大c(A,k)的。 这样我们对树进行两次遍历之后就能求出所有结点的Value值，只需找Value最大的结点输出就行了。 （程序请参见附录）小结： 有根树的动态规划实现起来是十分简单的。而对于无根树的动态规划，我们则可以先将无根树转为有根树，然后再考虑“上方子树”的问题。在考虑“上方子树”问题的时候应充分利用树的性质，找到高效解决这个问题的方法，否则这里将会成为瓶颈。二、树的构造 树的特殊性质使得我们在解决树的问题时经常用到构造的算法。寻求树的构造方法以及证明方法的过程是十分有趣的，下面举几个例子简单谈谈树的构造问题。例5给出一棵二叉树，证明一定可以把它的结点分成三个部分A,B,C，使得每一个结点和他的儿子以及他的兄弟（如果有的话）处于不同的集合，使得Max|A|,|B|,|C|-Min|A|,|B|,|C|1。 分析：这题考查的是二叉树的性质，对于树的证明类题目，归纳法是比较常用的，这题也不例外。 我们先对命题进行加强，加强部分为：“根结点位于集合A，且满足Max|A|,|B|,|C|=|A|”。1、当树为空的时候显然成立：|A|=|B|=|C|=0；2、当树只有一个根结点X，3、无左右儿子时，4、令A=X,B=C=便能满足要求；5、当树的结点数大于1时，6、设根结点为X，7、其左右儿子分别为Y,Z，8、且X的左右子树均满足命题，9、则：设左子树的三个集合为A1,B1,C1，Y位于集合A1中；右子树的三个集合为A2,B2,C2，Z位于A2中。则有|A1|B1|C1|,|A2|B2|C2|。不妨设|A1|=m,|A2|=n。则可能出现如下这集中情况： (|A2|,|B2|,|C2|) (|A1|,|B1|,|C1|)(n,n,n)(n,n,n-1)(n,n-1,n)(n,n-1,n-1)(m,m,m)A=B1+C2+X B=A1+B2 C=A2+C1A=C1+C2+X B=A1+B2 C=A2+B1A=B1+B2+X B=A1+C2 C=A2+C1A=B1+B2+X B=A1+C2 C=A2+C1(m,m,m-1)A=C1+C2+X B=A1+B2 C=A2+B1A=B1+C2+X B=A1+B2 C=A2+C1A=C1+C2+X B=A1+B2 C=A2+B1A=B1+B2+X B=A1+C2 C=A2+C1(m,m-1,m)A=B1+B2+X B=A1+C2 C=A2+C1A=C1+C2+X B=A1+B2 C=A2+B1A=B1+C2+X B=A1+B2 C=A2+C1A=C1+C2+X B=A1+B2 C=A2+B1(m,m-1,m-1)A=B1+B2+X B=A1+C2 C=A2+C1A=B1+B2+X B=A1+C2 C=A2+C1A=C1+C2+X B=A1+B2 C=A2+B1A=B1+C2+X B=A1+B2 C=A2+C1无论出现哪种情况，都存在方案使得新的集合A,B,C符合命题。这样就用归纳法证明了题目中命题的。 在进行树的构造的时候最关键的是抓住树的特性，例如下面这一题：例6树重建 (Rebuild) 给出一棵标号树的BFS序列和DFS序列，设计一个算法重新建立这棵树（结点数n1000）。当某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问。例如一棵树的BFS序列为43512876，DFS序列为43172658，则一棵满足条件的树如右图所示。输入格式第一行输入结点数n。第二行n个用空格隔开的整数，描述这棵树的BFS序列；第三行n个用空格隔开的整数，描述这棵树的DFS序列。输出格式一共输出n-1行，每行两个整数i,j描述一条边，表示第i个结点与第j个结点之间连一条边。样例输入84 3 5 1 2 8 7 64 3 1 7 2 6 5 8样例输出4 55 84 33 22 63 11 7 分析：我们曾经遇到过相似的题目，给出一棵二叉树的先序，中序，后续遍历中的其中两种，要你还原这棵二叉树。而这题改为了给出DFS和BFS序列，虽然形式上变了，但是原理还是相似的，我们只需抓住树的性质和充分利用这两个序列的特性就能把这种题目解决。 拿题目数据做例子。首先，无论是BFS序列还是DFS序列，第一个点都必定是根结点。接着我们看BFS序列，跟在根结点4后面的连续若干个结点就是4的儿子结点，但是究竟有多少个是4的儿子呢？首先，题目中的一个条件说：“某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问”，因此4的儿子应该是按由小到大出现在BFS序列中的。后面31，所以1就肯定不是4的儿子。然而即使后面若干个数满足升序的条件，也不一定全都是4的儿子，这时我们就要借助DFS序列了。因为DFS的规律是遍历完一棵子树才到另一棵，所以4的儿子在DFS序列中也是按由小到大出现，只是它们之间可能被若干个结点隔开罢了。根据这两个条件，我们就能判断哪些是4的儿子了。例如在BFS序列中紧挨着4出现的3,5，在DFS序列中也是按照由小到大的顺序先出现3，再出现5，因此3,5都是4的儿子。 接下来怎么做呢？由于4的儿子都确定了，剩下的就是把4的每一棵子树都确定下来，而这就是一个子问题了。若我们确定了根结点有k个儿子，若第i个儿子在DFS中的位置为P1，第i+1个儿子在DFS中的位置为P2，则在DFS序列中位置P1与P2之间的所有结点就是以第i个儿子为根的子树的结点。而我们可以建立一个队列，每确定一个结点就把它加到队列里面去，模拟BFS的过程。在模拟广搜的过程中，若当前要处理的结点为k，由于以k为根的整棵子树在DFS序列中是连续的一段，而究竟是那一段在前面的广搜过程中是可以顺带求出的。然后我们利用BFS序列和DFS序列中连续的一段确定出k的所有儿子，并加到广搜队列里面。直到广搜结束，问题就解决了。不难发现，这样做的时间复杂度是O(n*Log2n)的。 （程序请参见附录） 下面再举一个树的构造的例子：例7毛毛虫 (Caterpillar) 毛毛虫是含N(N10000)个结点的一棵树，它包含一条主链，使得所有点要么在主链上，要么和主链上的某个结点相邻。如图所示有两只合法的毛毛虫，灰色的结点代表主链。 我们希望给毛毛虫的每个顶点标号1,2,3,N，使得所有边的两端结点标号差的绝对值恰好包含了1,2,3,N-1，每个数正好一次。如下图所示是一个合法的标号。边上的数字为标号差。输入格式第一行是两个整数n,m，(1mn10000)，其中n为结点个数，m为主链上的结点数。接下来的m行每行一个整数k，描述主链上的结点。第i+1行的结点与第i行的结点有边相连。接下来n-m行描述的是支链上的结点，每行两个整数i,j，其中i是支链上的结点，j是主链上的结点，表示i与j之间有边相连。输出格式共输出n行，每行一个整数k。第i行的k表示第i个结点的标号为k。样例输入9 412593 24 26 57 58 5样例输出815294637 分析：这种是一道十分明显的构造类题目，和树的关系密切，而且题目中的树也十分特殊“所有点要么在主链上，要么和主链上的某个结点相邻”。因此我们应当抓住这一特性来解题。 以题目数据作为例子。主链在这道题里面占据着十分重要的地位，我们可以从主链入手。不妨让结点1的标号为1，记为F1=1。由于我们要使1到N-1这N-1种差值都出现一次，因此标号为n（也就是9）的结点必定和标号为1相邻。所以2的标号就是9了F2=9。而要出现7这个差值，要么1,8相邻，要么2,9相邻，而与标号为1的结点相邻的结点都已经标好了号，于是只能够让2,9相邻。所以我们不妨让结点3的标号为2F3=2。同理，要出现6这个差值，要么1,7相邻，要么2,8相邻，要么3,9相邻。而与标号为1和标号为2的结点相邻的结点都已经标了号，因此只能让3,9相邻，我们不妨让结点4的标号为3F4=3。依此类推，要出现5这个差值，只能让4,9相邻，即结点5的标号为4F5=4。要出现4这个差值，只能让4,8相邻，不妨让结点6的标号为8F6=8。接着，要出现3这个差值，只能是4,7相邻，不妨让结点7的标号为7F7=7。要出现2这个差值，只能让4,6相邻，不妨让结点8的标号为6F8=6。要出现1这个差值，只能让4,5相邻，于是结点9的标号为1F9=1。这样，我们就把所有点都标上了号，并且N-1中差值都出现了一次。 从上面的探索过程我们就能猜想到这道题目的解法：先从主链最左边的顶点入手，将他的标记设为1。接着按顺序依次处理主链上的每一个点，对每个点都进行如下处理：（设当前要处理的点为k）1、依次将与k相邻的支链点标号：（注意：与k相邻的主链点先别动。） 若剩余的标号都比k的标号大，则从剩下的标号中选择最大的数字作为当前支链点的标号。 若剩余的标号都比k的标号小，则从剩下的标号中选择最小的数字作为当前支链点的标号。2、将与k相邻的主链点标号：（当然是未标号的主链点。） 若剩余的标号都比k的标号大，则从剩下的标号中选择最大的数字作为当前主链点的标号。 若剩余的标号都比k的标号小，则从剩下的标号中选择最小的数字作为当前主链点的标号。 怎么证明这个算法的正确性呢？首先，一开始我们先将主链上的第一个点标为1，然后将与它相邻的某一个点标为了n。这样我们就获得了差值n-1。接下来证明剩余的差值都能获得。设前两次标的号为k1,k2(k1k2)，因此前一次我们获得的差值为k2-k1。而根据上述算法的特征，下一次标的号要么是k1+1，要么是k2-1。而k1+1是与k2相邻，k2-1与k1相邻，因此我们就能获得k2-k1-1的差值。而上述算法能够保证所有点均被标号。根据归纳法，所有的差值都能获取。 （程序请参见附录）三、总结 通过对树的动态规划与构造的分析，我们又加深了对树的认识。然而树的问题有很多类，是十分丰富多彩的，而且趣味性也很浓。由于篇幅有限，本文只能列举有限的一些例子，权当抛砖引玉，希望能激发大家对树的兴趣，进行更深入的研究。【参考文献】1、ACM网上题库：SGU (acm.sgu.ru)2、算法艺术与信息学竞赛 刘汝佳 黄亮 著 （清华大学出版社 2004年1月第一版）【附录】例1的程序13例2的程序15例3的程序17例4的程序20例6的程序23例7的程序25例1的程序134.pasProgram Sgu_134;Type Lion=xm; xm=Record Num,Value:Longint; Num是结点的编号，Value是该边连出去的子树的深度 Next:Lion; End;Var i,j,k,m,n,k1,k2,Min:Longint; p:Lion; a:array1.16000 of Lion; 存树中的边 List:array1.16000 of Longint; 可能有多个质心，保存质心的数组Function Go(x,Father:Longint):Longint; 遍历树的过程Var i,j,k,Sum:Longint; p,q:Lion;Begin Sum:=1; p:=ax; While pNil do Begin if p.NumFather then Begin if p.Value=0 then p.Value:=Go(p.Num,x); 计算该子树的深度 inc(Sum,p.Value); 计算以x为根的子树的总结点数 End else q:=p; 把x指向父亲的那条边存起来 p:=p.Next; End; q.Value:=n-Sum; 计算x的上方子树结点数 Go:=Sum;End;Procedure Init; 读入数据和预处理过程Begin readln(n); for i:=1 to n do ai:=Nil; for i:=1 to n-1 do Begin readln(k1,k2); New(p); p.Num:=k2; p.Value:=0; p.Next:=ak1; ak1:=p; New(p); p.Num:=k1; p.Value:=0; p.Next:=ak2; ak2:=p; End; Go(1,0);End;Procedure Main; 寻找质心的过程Var i,j,k,Max,Num:Longint; p:Lion;Begin Min:=Maxlongint; Num:=0; for i:=1 to n do Begin Max:=0; p:=ai; While pNil do Begin if p.ValueMax then Max:=p.Value; p:=p.Next; End; if MaxMin then Begin Min:=Max; Num:=1; List1:=i; End else if Max=Min then Begin inc(Num); ListNum:=i; End; End; writeln(Min, ,Num); for i:=1 to Num do write(Listi, ); writeln;End;BeginInit; Main;End.例2的程序149.pasProgram Sgu_149;Const Maxn=10000; 最大结点数Type Lion=xm; xm=Record Num,Long,Value:Longint; Num,结点编号;Long,网线长度;Value,该边连出去的子树深度 Next:Lion; End; Lion1=Record k1,k2:Longint; k1存储最大值，k2存储第二大值 End;Var i,j,k,m,n,k1,k2:Longint; p:Lion; a:array1.Maxn of Lion; 存树中的边 Max:array1.Maxn of Lion1; 保留每个结点的最深的两棵子树的深度Function Go(x,Father:Longint):Longint; 求以x为根结点的子树深度Var Max:Longint; p:Lion;Begin Max:=0; p:=ax; While pNil do Begin if p.NumFather then Begin if p.Value=0 then p.Value:=p.Long+Go(p.Num,x); if p.ValueMax then Max:=p.Value; 记录最大的深度 End; p:=p.Next; End; Go:=Max;End;Procedure Init; 读入数据和预处理Var p:Lion;Begin readln(n); for i:=1 to n do ai:=Nil; for i:=2 to n do Begin readln(k,j); New(p); p.Num:=k; p.Long:=j; p.Value:=0; p.Next:=ai; ai:=p; New(p); p.Num:=i; p.Long:=j; p.Value:=0; p.Next:=ak; ak:=p; End; Go(1,0);End;Procedure Main;Var i,j,k:Longint; p,q:Lion;Begin Fillchar(Max,sizeof(Max),0); for i:=1 to n do Begin p:=ai; While pNil do 先求出以i为根的树最深的两棵子树的深度 Begin if p.ValueMaxi.k1 then Begin Maxi.k2:=Maxi.k1; Maxi.k1:=p.Value; end else if p.ValueMaxi.k2 then Maxi.k2:=p.Value; p:=p.Next; End; p:=ai; While pNil do 求出i的所有儿子的上方子树的深度 Begin if p.Numi then 判断p.Num是否是i的父亲，如果是就没必要求上方子树 if p.Value=Maxi.k1 then Maxp.Num.k1:=Maxi.k2+p.Long else Maxp.Num.k1:=Maxi.k1+p.Long; 如果子树p.Num是最深的子树，则它上方子树的深度为第二深的子树深度加上p.Long；否则它的上方子树深度等于最深的子树的深度加上p.Long p:=p.Next; End; writeln(Maxi.k1); 输出解 End;End;Begin Init; Main;End.例3的程序Jerrygen.pas$n+,s-,r-,q-,i-Program Jerrygen;Const Maxn1=400000; 由于一条边要存两次，因此最大边数=最大结点数*2 Maxn=200000; 最大结点数Type Lion=Record Num,Next:Longint; Num,结点编号;Next,指针，用数组来模拟内存操作 Long,Value:double; Long,边的长度;Value,子树深度 End;Var i,j,k,m,n,k1,k2,tot:Longint; Max:double; a:array0.Maxn1 of Lion; 记录树的边 Best:array0.Maxn,1.3 of double; 记录以结点i为根时最深的前三个深度 From,Start:array0.Maxn of Longint; From,记录以i为根时最深的那棵子树的根结点是哪个;Start,记录每个结点的邻接表起点在a数组的位置（用数组模拟内存） Buf:array0.4095 of char; 文件读写缓存Procedure Add(k1,k2,k:Longint); 加入边的过程Begin inc(tot); atot.Num:=k2; atot.Long:=k; atot.Value:=0; atot.Next:=Startk1; Startk1:=tot;End;Procedure Init; 读入数据和预处理Begin assign(input,jerrygen.in); Settextbuf(input,buf); reset(input); assign(output,jerrygen.out); rewrite(output); Readln(n,m); Fillchar(Start,sizeof(Start),0); tot:=0; for i:=1 to m do Begin Readln(k1,k2,k); Add(k1,k2,k); Add(k2,k1,k); End; Fillchar(Best,sizeof(Best),0); Fillchar(From,sizeof(From),0);End;Function Deal(x,Father:Longint):double; 求以x为根的树的深度的函数Var p:Longint; Max:double;Begin p:=Startx; Max:=0; While p0 do Begin if ap.NumFather then Begin ap.Value:=Deal(ap.Num,x)+ap.Long; if ap.ValueMax then Max:=ap.Value; 保留深度最大值 End; p:=ap.Next; End; Deal:=Max;End;Procedure GetAns(x,Father:Longint;Long:double); 求上方子树深度及答案Var p:Longint; Value:double;Begin if FromFatherx then Bestx,1:=BestFather,1+Long else Bestx,1:=BestFather,2+Long; 若x是最深的子树，则取第二深度加上x与他父亲的距离；否则取第一深度加上x与他父亲的距离 Fromx:=Father;赋初值，一开始最深的子树就是x的上方子树（因为其他的还没考虑） p:=Startx; While p0 do 保留前三深的深度 Begin if ap.ValueBestx,1 then Begin Bestx,3:=Bestx,2; Bestx,2:=Bestx,1; Bestx,1:=ap.Value; Fromx:=ap.Num; End else if ap.ValueBestx,2 then Begin Bestx,3:=Bestx,2; Bestx,2:=ap.Value; End else if ap.ValueBestx,3 then Bestx,3:=ap.Value; p:=ap.Next; End; Value:=Bestx,1+2*Bestx,2+Bestx,3; 计算路程 if ValueMax then Max:=Value; 保留最大路程 p:=Startx; While p0 do 调用x的儿子的GetAns过程 Begin if ap.NumFather then GetAns(ap.Num,x,ap.Long); p:=ap.Next; End;End;Procedure Main; 主过程Var i,j:Longint;Begin Deal(1,0); Max:=0; GetAns(1,0,0); Writeln(Max:0:0); Close(Output);End;Begi