Solution Found!
You are given a tree T = (V, E) along with a designated root node r V . The parent of
Chapter 3, Problem 3.20(choose chapter or problem)
You are given a tree T = (V, E) along with a designated root node r V . The parent of any nodev 6= 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 pk(v) = pk1(p(v)) and p1(v) = p(v) (so pk(v) is the kth ancestor of v).Each vertex v of the tree has an associated non-negative integer label l(v). Give a linear-timealgorithm to update the labels of all the vertices in T according to the following rule: lnew(v) =l(pl(v)(v)).
Questions & Answers
QUESTION:
You are given a tree T = (V, E) along with a designated root node r V . The parent of any nodev 6= 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 pk(v) = pk1(p(v)) and p1(v) = p(v) (so pk(v) is the kth ancestor of v).Each vertex v of the tree has an associated non-negative integer label l(v). Give a linear-timealgorithm to update the labels of all the vertices in T according to the following rule: lnew(v) =l(pl(v)(v)).
ANSWER:Step 1 of 3
The problem comes down to how you find the l(v)-the parent of a node v, for all 