You are given a tree of N nodes and a special node B. Each node v has asocciated an unique integer, let’s denote this integer by f(v). Your task is to provide an answer for each of q following queries. A single query consists of two integers, A and P. Let D(v) denotes the minimum distance between the unique path from A to v in the tree i.e. the minimum distance between A and any node on the path. The answer for a single query (A, P) is a node v for which f(v) = P and D(v) is minimum among all such nodes. If there is more than one such node, you should return the one with minimum number.
Root a tree in B using dfs. During this dfs compute dp[v][c] := minimum node u in v’s subtree for which f(u) = c or INF if there is no such node.
Using second dfs, for each v and c, compute ans[v][c] := dp[c] where u is the first node on the path from v to B for which dp[c] != INF or -1 if no such node exists
For each query (A, P), return ans[A][P].
The method mentioned in quick explanation is straightforward, but let’s take a look why it works.
Consider a single query (A, P). Let dist(u) be a distance from node u to the root of the tree, i.e. to node B. Let’s assume that the result for this query is a node v. Then D(v) <= dist(A), because A is the first node of the path to v. Since we are looking for a v for which D(v) is maximal, the best thing we can do is to search for it in A’s subtree, because if there exists a v in that subtree for which f(v) = P, then D(v) = dist(A) and we cannot do better. If there is no such v in A’s subtree, we search (based on the same argument) for the next greatest value of D(v) in a subtree rooted in the parent of A. We continue this process unless we find v, for which f(v) = P or we reach node B. If we reach B and doesn’t find a node v for which f(v) = P, the answer is -1.
In order to do that, we compute dp[v][c] := minimum node u in v’s subtree for which f(u) = c or INF if there is no such node.
If implemented naively, that method has O(n^2) running time, which may pass here, but we can do better.
Using the second dfs, for each v and c, compute ans[v][c] := dp[c] where u is the first node on the path from v to B for which dp[c] != INF or -1 if no such node exists. This is similar to path compression in union-find data structure.
Using ans table, we can answer any query in O(1) time.
Time complexity is O(N * K) because for each K, we visit every edge a constant number of times during precomputational phase and we answer each query in constant time.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be uploaded soon.
To be uploaded soon.