Finding the longest path in an undirected weighted tree I have a tree where each edge is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the sum of the weights of the edges in the path is maximum). There's no restriction on what node the path starts or ends.
I have a possible algorithm, but I am not sure it works and I am looking for a proof. Here it is:


*

*Select an arbitrary node u and run DFS(u) to find the maximum weight simple path that starts at u. Let (u, v) be this path.

*Run DFS(v) to find the maximum weight simple path that starts at v. Let this path be (v, z).


Then (v, z) is a simple path of maximum weight. This algorithm is linear in the size of the graph. Can anyone tell me if it works, and if so, give a proof?
Note: The Longest Path Problem is NP-Hard for a general graph with cycles. However, I only consider trees here.

Good idea. In fact, if all the edge weights are 1, this is a standard way to find the diameter of a tree. Unfortunately, your two-DFS algorithm has a problem when the edge weights can be negative.
Consider, for example, the following edge-weighted tree:

If we do a DFS starting at $u=v_0$ we find that there are two maximal paths from $u$: to $v_1$ and to $v_3$, both with weight 2. Doing the second DFS from $v_1$ yields the maximal path $\langle v_1, v_0, v_2, v_3\rangle$ of weight 4, but doing the DFS from $v_3$ gives the maximal path $\langle v_3, v_2, v_4\rangle$ which has weight 5.
I'm fairly sure you could modify your algorithm so that it gives a maximal path, but I suspect that the modified version would no longer be linear in the number of vertices. Gotta think about that.
