Im having some trouble coming up with an algorithm for the following scenario:
Suppose you are given a tree with root r. Each node has a label l(v) that is a nonnegative integer. Come up with an algorithm to relabel each vertex v so that $l_{new}(v)=l(w)$ where w is the kth ancestor of v for k = l(v). Root r is its own parent.
One thing Im thinking is somehow doing a kind of topological sort and putting the sorted order in an array, from which you can go backward a specific amount (given by a formula) to find the kth ancestor but that doesnt sound right.
I was also thinking running through the tree with DFS and keeping a mapping of a node and its ancestors (or conversely, descendants) in order, so then you can just index into the list to get the kth ancestor. That seems more right but Im not completely sure.
Would love some guidane - I feel like my intuition is kinda halfway there, but still strugglign
"I was also thinking running through the tree with DFS and keeping a mapping of a node and its ancestors (or conversely, descendants) in order, so then you can just index into the list to get the kth ancestor. That seems more right but Im not completely sure."
This works.
In a tiny bit more detail: Build an array $L[i]$ where $L[0] = L[1] = ... = L[k-1] = l(r)$. Now perform a DFS where we add/remove entries to the array as we traverse.