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.
 A: Consider the following algorithm, where we start at terminal nodes and keep removing them while accounting for the corresponding paths. For each node $v$, we store $2$ longest paths we have obtained so far (say of length $l_1(v)$ and $l_2(v)$, with $l_1 \geq l_2$), which end at that node. Initially set all these values to zero.


*

*Let $v$ a terminal vertex in the tree and let $(u,v)$ be the edge touching it.

*Set $l = l_1(v) + w(u,v)$.

*Modify $l_1(u)$ and $l_2(u)$ by picking the largest two among $l_1(u)$, $l_2(u)$ and $l$.

*Remove the terminal node $v$ and its edge $(u,v)$ from the tree. If the tree is not empty (no edges), go back to step $1$.


When all edges have been removed, we can show that maximum path length is given by $\max {(l_1(v) + l_2(v))}$, over all nodes $v$ in the original tree. Each vertex and edge is visited exactly once and all the operations are constant time, so the algorithm is linear in the number of vertices.
I assumed here that an empty path (path with no edges) is admissible and has length $0$ (for example, when all edge weights are negative, empty path is the longest). But if you only want non-empty paths, you could change the initialization of $l_1$ and $l_2$ values for all nodes to $-\infty$ instead of $0$.
A: 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.
A: I want to propose a different $\mathcal{O}(n)$ algorithm. We will pick any node $u$ and start dfs from it. Our $dfs$ will return two things.


*

*Longest simple path with $u$ as the end node of the simple path which we will call as $V_{1u}$

*Longest simple path in the subtree $u$ which we call as $V_{2u}$


Let $u$ have $i$ children. $u_1, u_2, \dots, u_i$. Our $dfs(u_j)\ \forall\ 1 \leq j \leq i$ will recursively calculate answer for $u_1, u_2, \dots, u_i$. For every child, we will get two values as mentioned before. Now, we will use these values to calculate the {answer pair} for node $u$ using the following way


*

*Longest simple path with $u$ as the end node($V_{1u}$) will be $max(w(u, u_j)
    + V_{1u_j}) \forall 1 \leq j \leq i$ which will be calculated in the $\mathcal{O}(i)$ time.

*Longest simple path in $u's$ subtree($V_{2u}$) will be the $max$ of the
following things :- $max(V_{2u_j})$, $V_{1u}$, longest simple path with $u$ as one of it's nodes
To Calculate Longest simple path with $u$ as one of its nodes (i.e. Simple paths going between two of its childrens) will be simply $max(w(u, u_j) + V_{1u_j} + w(u, u_k) + V_{1u_k}) \forall 1 < j < k < i$. So, we have to essentially select maximum and second maximum from $w(u, u_j) + V_{1u_j}$ which we can do in linear time(with respect to the size of the children of $u$). Hence, we can return both the values in a total of $O(n)$ time. 
