1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Can you spell out the problem better? What are your thoughts on this? $\endgroup$ – 6005 Apr 15 '20 at 2:29
  • $\begingroup$ OK. I have a weighted tree, and on each edge written number - positive or negative number. And I want to find a path so that the sum(sun of numbers on edge) is equal to zero, and the amount of edges along which I went was the maximum. $\endgroup$ – Maxim Apr 15 '20 at 2:46
  • $\begingroup$ Is the tree directed from a root or just an undirected acyclic graph? For example, can a valid path start at a leaf and end at a different leaf? $\endgroup$ – Aaron Rotenberg Apr 15 '20 at 3:33
  • $\begingroup$ This problem is very similar to a problem name Race that appeared on the 2011 edition of the International Olympiad in Informatics, however the difference is that it looks for the minimum number of edges instead of maximum, and it asks for a path of length $K$, rather than $0$. However, I believe that you can use the same technique used to solve the Race problem. Here is link to the problem: ioinformatics.org/files/ioi2011problem2.pdf $\endgroup$ – someone12321 Apr 15 '20 at 9:07
2
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ How can you build those dictionaries so efficiently? $\endgroup$ – someone12321 Apr 15 '20 at 8:58
  • $\begingroup$ An AVL tree suffices. It supports insertions, deletions and lookups in $O(\log n)$ time, where $n$ is the number of elements currently stored. If each node also keeps an integer offset to be applied to the keys of all its descendants, then the additional operation (increasing all keys in the tree by a constant) can also be performed in constant time. $\endgroup$ – Steven Apr 15 '20 at 9:02
  • $\begingroup$ Can you propose a pseudo-code for the processing, because keep in mind that you need to build this structure for each node, and each node can have up to $O(N)$ nodes in their subtree. Merging two different AVL trees doesn't seem easily possible too. $\endgroup$ – someone12321 Apr 15 '20 at 9:04
  • $\begingroup$ I'm not merging AVL trees. When a vertex $v$ with $k$ children is visited, then all nodes in the dictionaries (AVL trees) of the 2nd to last child added moved into the dictionary (AVL tree) of the first child $u$ (which is the node with more keys in its dictionary, w.l.o.g.). The resulting AVL tree is now the dictionary of vertex $v$. Notice that it is not a copy of the AVL tree of $u$ but the same tree with extra vertices added. This can be done since the dictionary of $u$ will never be needed anymore. $\endgroup$ – Steven Apr 15 '20 at 9:10
  • $\begingroup$ But won't you then add all those nodes again in other dictionaries, when solving for the parent of $v$, and the parent of the parent of $v$.. $\endgroup$ – someone12321 Apr 15 '20 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.