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.

Thanks very much.

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.

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. I think something needs to be done in the post-visit part of DFS traversal, but I don't know how to determine the $l(v)$-th parent of node $v$ for all $v$ in linear time.

Thanks very much.

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.

Thanks very much.