不知道这里的java高手水平到底如何 小弟最近在研究这道题： http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3283 就是weighted trees,要求找出weight总和最大的分支.

各位有兴趣的可以写写看，我觉得就是些recursive的语句

欢迎各位赐教

多谢

各位高手一定尽快看一下啊~~~多谢

developer has designed a subdivision within a city such that all roads connect at intersections in a treelike design. This is to prevent all petrolhead hooligans from disturbing the residents by not having any road loops for races. Only the entering intersection is connected to the rest of the city. The developer is selling off land alongside roads between adjacent intersections. A real estate agent has produced a book indicating the expected dollar profit (positive, zero or negative) that can be obtained by purchasing the land alongside each road.

Potential buyers want to maximize their profit, but prefer to buy a contiguous stretch of land alongside a simple road chain that connects two intersections of the subdivision. Your task is to write a program to determine the maximum non negative profit that can be obtained this way, and return 0 if no such profit can be obtained.

As an example, consider the following representation of a subdivision, where road labels represent expected profits. In this scenario, the maximum non negative profit is 7, and can be obtained alongside the road chain between the intersections #2 and #5:

http://acmicpc-live-archive.uva.es/nuevoportal/data/p3283.jpg （他提供的图的地址）

Input Input for this problem consists of a sequence of one or more scenarios. Each scenario contains two or more lines.

The first line contains an integer n , 1n500000 , indicating the number of intersections, including the entrance intersection, implicitly labelled 0. This is then followed by one or more lines, containing n - 1 pairs of integers. All integers are separated by single spaces or newlines. The y -th intersection is defined by the y -th pair of integers `x p ', where 1y < n , 0x < y , -1000p1000 . This pair indicates a road segment between y and a previously defined intersection, x , with a profit value p .(Attention, for this program, input lines may contain up to 4096 characters each!) The input will be terminated by a line consisting of one zero (0). This line should not be processed.

Output Output will be a sequence of lines, one for each input scenario. Each line will contain an integer, indicating the maximum nonnegative profit, over all possible simple road chains connecting two intersections of the subdivision. Write zero (0) if no profit can be obtained.

Sample Input

6 0 -1 1 3 0 2 1 1 1 4 6 0 2 0 1 0 2 0 1 1 1 5 0 1 1 -3 0 -2 1 -2 5 0 -1 1 -3 0 -2 1 -2 10 0 -1 0 -1 0 0 1 3 1 4 2 4 2 2 3 3 3 3 0

Sample Output

7 5 1 0 7

And here's some advice I got from someone else:

Transform the tree into a rooted tree by designating an arbitrary node as the "root" (for example, node "0" in your example). Direct all edges away from the root, namely, from a parent to its children. a subtree at node i (denoted by T_i) contains the node i and all of its descendants.

Now, compute an optimal maximum weight path (MWP) for the entire tree starting from the leaves (those with no children) and up. or each subtree T_i rooted at node i, compute the following

1. A MWP in T_i ending at i: This can be computed by extending MWPs in its children subtrees ending at its children.

2. A MWP in T_i containing i as an intermediate node: Similar to (1), by selecting two of i's best children extension.

3. A MWP in T_i not containing node i: Select the best MWP from among its children subtrees.

以上的建议　　可能不是最快的algorithm，但我想了一下应该是可以解决问题的 你们觉得呢