Finding the longest path of sum $0$ in a weighted tree

Question

How to find the longest path with the sum $0$ in a weighted tree (where each edge is labeled with an integer weight)?

In other words, I want to find a path so that the sum (sum of numbers on edges) is equal to zero, and the amount of edges along which I went is the maximum.

Answer 1

If the (simple) path needs to go from the root to a descendant:

Perform BFS or a preorder DFS visit of your tree and, for each vertex $v$, record:

• the length $\ell(v)$ of the unique path from the root of the tree to $v$; and
• the depth $d(v)$ of $v$ in $t$.

This can be done in constant time per vertex since, if $v$ is the root $\ell(v)=d(v)=0$, otherwise $\ell(v) = \ell(u) + w(u,v)$ and $d(v) = d(u) + 1$, where $u$ is the parent of $v$.

Return the vertex $v$ for which $\ell(v)=0$ and $h(v)$ is maximized. The total time spent is linear.

If the (simple) path needs to go from an ancestor to a descendant:

Perform a preorder DFS visit and maintain a dictionary $D$ that stores the ancestors $u$ of the current vertex $v$. The key of a vertex $u$ in $D$ is the length $\ell(u)$.

When an edge $(u,v)$ is traversed moving away from the root, add $\ell(u)$ to $D$. When an edge $(u,v)$ is traversed (moving towards the root) remove $\ell(u)$ from $D$. In case of ties in $D$ break them in favor of the lowest vertex.

When a vertex $v$ is visited, we want to search $D$ for an ancestor $u$ of $v$ with key $\ell(u) = \ell(v)$, meaning that the path from $u$ to $v$ has length $\ell(v) - \ell(u) = 0$. This can be done in $O(\log H) = O(\log n)$ time, where $H$ is the height of the tree.

The overall time complexity is then $O(n \log H) = O(n \log n)$.

If the (simple) path can be arbitrary:

For each vertex $v$ compute its depth $d(v)$ in any standard way.

Perform a postorder DFS visit and, for each vertex $v$, maintain a dictionary $D_v$ that stores all descendants $z$ of $v$. The key of $z$ is the distance from $v$ to $z$. Break ties in favor of vertices $z$ with larger $d(z)$. In addition to the standard operations, you can also assume that $D$ is able to increase all its keys by a constant amount in $O(1)$ time.

When $v$ is visited and $v$ is a leaf, $D_v$ contains only $v$ itself with key $0$. Otherwise, let $u_1, \dots, u_k$ be $v$'s children and assume w.l.o.g. that $u_1$ maximizes $|D_{u_1}|$. Construct $D_v$ as follows:

• Initially $D_v = D_{u_1}$. Notice that $D_{u_1}$ will not be used anymore. This operation amounts to renaming $D_{u_1}$ to $D_v$.
• Increase all the keys in $D_v$ by $w(v, {u_1})$.
• Add $v$ with key $0$ to $D_v$.
• The vertex $z$ with key $0$ in $D_v$ is such that the path from $v$ to $z$ has length $0$ and the number of edges from $v$ to $z$ is maximized (remember our tie-breaking rule). This is a candidate path.

• For each $u = u_2, \dots, u_k$:

  • For each vertex $a$ with key $\ell_a \in D_u$:

    • Check whether there is a vertex $b$ in $D_v$ with key $\ell_b = -\ell_a - w(v,u)$. If this is the case then there is a candidate path from $a$ to $b$ of length $0$ and hop-length $d(a) + d(b) - 2d(v)$.

  • For each vertex $z$ with key $\ell_z \in D_u$:

    • Move vertex $z$ from $D_u$ to $D_v$. Its new key in $D_v$ is $\ell_z + w(v,u)$.

Return the best candidate path seen during the visit.

To bound the time complexity notice that, apart from a $O(n \log n)$ term needed to add the vertices $v$ into $D_v$, it is dominated by the complexity needed to move vertices $z$. When a vertex $v$ is moved from $D_u$ to $D_v$, the size of $D_v$ will be at least twice the size of $D_u$. This means that each vertex can be moved at most $O(\log n)$ times.

The overall time complexity is therefore $O(n \log^2 n)$.