Finding the longest path in an undirected node-weighted tree

Question

I have a tree where each node 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 nodes 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:

1)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.

2)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.

Answer 1

No, your algorithm does not work sometimes.

Here is a counterexample. Let graph $G$ have five weighted nodes, $A\mapsto 1$, $B\mapsto -1$, $C\mapsto 0$, $D\mapsto 1$, $E\mapsto 1$. There are four edges, $AB$, $BC$, $CD$ and $CE$.

Let us run your algorithm.

1. Select node $B$ and run DFS($A$). We may get the maximum weight simple path $B, A$, whose weight is 0.
2. Run DFS($A$), we may find the maximum weight simple path that starts at $A$, which is $A, B, C, D$, whose weight is 1. That path is returned.

However, the simple path with the maximum weight is actually $D,C,E$ whose weight is $2$.