You are not logged in. Please login at www.codechef.com to post your questions!

×

# PROBLEM LINK:

Author: Kamran Maharov
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

MEDIUM

Trees, dfs

# PROBLEM:

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.

# QUICK EXPLANATION:

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[u][c] where u is the first node on the path from v to B for which dp[u][c] != INF or -1 if no such node exists

For each query (A, P), return ans[A][P].

# EXPLANATION:

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[u][c] where u is the first node on the path from v to B for which dp[u][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:

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.

# RELATED PROBLEMS:

To be uploaded soon.

This question is marked "community wiki".

asked 15 Dec '14, 19:27

74485097
accept rate: 12%

14 Answers:
 3 We can also use a simple observation that value of G(i) while going from city u to v will be always equal to the distance of LCA(u,v) from the root of the tree(king city) which can be precomputed using BFS from root. So while going from city u to buy a product P we will store all possible values of G(i). The target_G(i) will be the maximum amongst all G(i)'s. So if target_G(i) appears multiple times we'll simply print the city with lowest index otherwise the one that is contributing to target_G(i) C++ Implementation answered 15 Dec '14, 20:39 4★divyank1 30●1●3 accept rate: 0% My C++ implementation is : http://www.codechef.com/viewsolution/5575749 (20 Dec '14, 15:59)
 1 Alternatively any sub-quadratic implementation of precomputing the LCAs of the tree (rooted at B as mentioned above) suffices. Here's an awesome article on all the different ways this can be achieved: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor Going for simplicity, the < O(N log N), O(log N) > implementation (i.e. O(N log N) pre-computation and O(log N) query) easily suffices for the given bounds. Great problem btw :D answered 17 Dec '14, 04:30 4★Amlesh 239●3 accept rate: 0%
 0 Can someone find the error in this code http://www.codechef.com/viewsolution/5611889. The approach is very similar to the one given in the editorial above. answered 18 Dec '14, 00:16 3★guptash 1 accept rate: 0%
 0 My soultion is based on finding BFS from the root and then finding distance of LCA of chef city and other city ,from the root.This is giving TLE. Here is my solution. But, a similar got accepted as commented by divyank above. What can be wrong in my code? Both the solution are nearly same. answered 18 Dec '14, 01:56 40●1●2●9 accept rate: 0% Similarly, I can't understand why my O(n*n) solution is getting TLE http://www.codechef.com/viewsolution/5625973 (21 Dec '14, 15:04)
 0 I don't know why so many DP based solutions this time in the challenge! :/ Our editorialist must be great at it. answered 20 Dec '14, 19:19 43●1●4●18 accept rate: 0%
 0 Gives good running time without 2nd DFS, just use the union-find path compression trick per query.. performs better in amortize terms. http://www.codechef.com/viewsolution/5641262 answered 24 Dec '14, 07:45 61●1●1●5 accept rate: 14%
 0 Hey, in the test case of the problem "Chef Under Pressure" the last input is "8 4" , which means that the chef will stay in the city number 8 and want product number 4. The city 8 itself has product 4 so he need not move to any other city to get it. But the output states that he should go to city number "4" to get it. Why is it so? answered 01 Sep '15, 05:40 1 accept rate: 0%
 0 Can you provide data set for the first test? I'm getting WA for this case and really don't know how can it be. I have correct results for all other tests in the first group and time-limit-exceeded for all tests in the second group. answered 15 Jan '16, 21:57 1 accept rate: 0%
 0 @krzysiek_t -same here; could anyone please provide what could be the first test case; and also I'm getting time limit exceeded in the second sub task, could anyone please elaborate how it could be? Thanks! answered 12 Apr '16, 21:21 1 accept rate: 0%
 0 I looks like no one has a solution that gets the first test case right? answered 15 Apr '16, 20:52 41●2 accept rate: 0%
 0 can You please write full forms of all uncommon abbriviations like dp[][] and INF and so on. Sorry if it's basic but i am a bt new. answered 02 Apr '17, 15:11 1 accept rate: 0%
 0 Hi All, I think there is an ambiguity in the question given and the problem explained above: PROBLEM EXPLANATION GIVEN ABOVE: "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." QUESTION GIVEN IN THE ACTUAL PROBLEM: suppose Chef will be living in the city A. For each city i, let G(i) be the smallest distance between B and any city on the unique path connecting cities A and i. The question talks about the minimum distance between B and any city on the unique path. Whereas the explanation above says minimum distance between A and any node on the path. I would like to know where the error is. In the question or the explanation provided above. As answer depends a lot on the comprehension. @pkacprzak it would be great if you clarify on the same. Thanks in advance. answered 02 May '17, 18:52 2★bhagzi 1 accept rate: 0%
 0 Can anyone please provide the first test case, I am getting wrong answer for it? answered 04 Jun '17, 16:53 3★prabalv 1 accept rate: 0% I don't think they give out test cases for problems. If you can't figure out the problem, post your code and ask your queries here :https://discuss.codechef.com/questions/97820/i-want-to-ask-a-question-ask-them-all-here (04 Jun '17, 16:58)
 0 Please Help i hv a solution for this problem which i think is right but when i submit it,codechef says it is wrong :/ my Approach : i used a bfs to find the shortest path between any 2 nodes,then for all nodes which have the required product i retrace its path to 'A' . while retracing i calculate the shortest distance of tht unique path from the capital,then i compare all such distances and output the path with max distance from capital please Help P.S i got the example question right answered 02 Sep '17, 02:05 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×2,595
×726
×708
×228

question asked: 15 Dec '14, 19:27

question was seen: 8,662 times

last updated: 02 Sep '17, 02:05