不知道这里的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，但我想了一下应该是可以解决问题的 你们觉得呢

不是不会做，只是没有兴趣做这种算法题。
你来这里不久，所以你不知道这里的情况，我们的兴趣在于写实用的应用程序。所以你看到了，我们是在两个层面上的。
当然我不反对做算法题，不过我认为算法题的意义在于将算法运用于实际的程序，纯粹的在算法里讨论，我实在没有兴趣。如果我们都写算法题，我的程序不会比你差，但是我承认，我不是一个算法的熟练工，最多我的解题的速度比你慢些而已。
这个世界上的确是有人纯粹地研究算法，他们甚至写不来应用程序，这种人也是需要的。但是这个世界上，几乎你能想到的最佳算法都有解了，所以在那里多花时间我个人认为没有多大意义，最多熟练你的编程速度而已，而且仅仅是在算法层面。
但是对于学习语言的初学者来讲，做做算法题是很有必要的。而且是必须的。

我弄过acm一段时间，现在懒的看全e文的，不如你把题目翻译一下！

ok,i c~~~~ 因为我也是初学 觉得练练这种题对以后应该会有所帮助 多谢你的意见~ 不知几时我才能到你的水平...

你看了那个图么 前面的都是铺垫 就是找出weight总和最大的那条分支(path)出来 因为我学的英文的 有些专业的中文java用语我不太会 不好意思 希望你能想出点思路阿

c'mon guys
没人有思路么.................

没时间看这么长的

学JAVA的算法好痛苦的

主要是小弟的Ｅ文太烂了，看帮助文档很费劲

至今只会用Ｃ写算法