Update labels of a tree depending on ancestors of nodes in linear time

Question

You are given a tree $T=(V,E)$ along with a designated root node $r \in V$.The parent of any node $v \ne r$, denoted $p(v)$, is defined to be the node adjacent to $v$ in the path from $r$ to $v$. By convention, $p(r) = r$.

For $k > 1$, define $p^k(v) = p^{k−1}(p(v))$ and $p^1(v) = p(v)$ (so $p^k(v)$ is the $k$-th ancestor of $v$).

Each vertex $v$ of the tree has an associated non-negative integer label $l(v)$. Give a linear-time algorithm to update the labels of all the vertices in T according to the following rule: $$l_{new}(v) = l(p^{l(v)}(v)).$$

This is problem 3.20 in Dasgupta's Algorithm.

My thoughts so far:

1. The problem comes down to how you find the $l(v)$-th parent of a node $v$, for all $v \in V$, in linear time.

2. Since chapter 3 is about depth first search, I'm trying to use it. The only way to get the parent once we have the child is to do something in the post-visit routine

   explore(v): 
     v.visited = true
     previsit(v)
     for all u adjacent to v:
       if u.visited == false:
         explore(u)
     postvisit(v)
   

3. If $l(v) = 3$ then somehow we need to send this information up 3 levels in the recursion. But depth first search only moves one level at a time. I don't know how we can preserve the information across multiple calls.

Answer 1

how we can preserve the information across multiple calls.

Excactly; we use a standard trick of functional programming and add additional parameters to the recursion.

Idea: Store (a copy of the) call stack in an array. Then, all ancestors of the current node are accessible in $O(1)$ time. You can do BFS or DFS.

Details: The main procedure starts at the root and creates an empty array of sufficient size:

relabel(T : Tree) {
  relabelH(T, 0, new Tree[T.size])
}

The second parameter stands for the current index in the array (i.e. recursion depth) which we use to determine the index of the $k$th ancestor. The actual work is done here:

relabelH(T : Tree, level : Int, ancestors : Tree[]) {
  ancestors[level] = T
  T.label = ancestors[max(0, level - T.label)].label

  for c in T.children {
    relabelH(c, level + 1, ancestors)
  }
}

Correctness: You can show by induction that ancestors[0..level-1] always contains the current node's ancestors in order from root to parent. Hence, the label update is correct. All nodes are reached (we do DFS) so the procedure is correct.

Running time: Every line in relabelH is executed once per visited node. Every individual line runs in constant time, assuming a reasonable implementation of Tree. The main call relabel(T) takes linear time (array initialization) plus the cost of the call to relabelH. In total, we get a running time in $\Theta(n)$ with $n$ the number of nodes (T.size).