Update labels of a tree depending on ancestors of nodes in linear time
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).