You can find the problem here.
Statement
This is a two-pass problem.
In the first pass, you are given an undirected tree with nodes, and you may relabel these nodes however you like; the only constraint is that all labels must be distinct.
In the second pass, you must implement a procedure that takes the following inputs:
- , a source node
- , the labels of the nodes directly adjacent to
- , a destination node And returns the unique label in such that lies on the path from to . In words, you must be able to route to with only the knowledge of adjacent labels at each step.
In order to earn full points, we must only use labels .
Solution
This essentially means that for an edge , using only the numbers , , and , we must be able to determine which nodes lie on the other side of this edge (i.e. closer to ). A natural way to do so is by assigning each subtree to a range of values.
You can find my code here.