HLPCHF Editorial

Setter: Dhananjay Raghuwanshi
Tester: Felipe Mota, Abhinav Sharma
Editorialist: Pratiyush Mishra

2859

Trees

PROBLEM:

Chef is the king of the kingdom named Chefland. Chefland consists of N cities numbered from 1 to N and (N-1) roads in such a way that there exists a path between any pair of cities. In other words, Chefland has a tree like structure.

Out of the N cities in Chefland, K (1 \leq K \leq N) are considered tourist attractions.

Chef decided to visit exactly (K-1) out of K tourist attractions. He wishes to stay in the city i (1 \leq i \leq N) such that the sum of distances of the nearest (K-1) tourist attractions from city i is as minimum as possible.

More formally, if Chef stays at city i and visits (K-1) tourist attractions denoted by set S, then, the value \sum_{j \in S} D(i,j) should be minimum.
Here, D(i,j) denotes the distance between cities i and j which is given by the number of roads between cities i and j.

Find the city in which Chef should stay. If there are multiple such cities, print the one with the largest number.

EXPLANATION:

This problem can be divided into two separate problems:

• Calculate, for each node, sum of distances of tourist locations from it.
• Calculate, for each node, maximum distance of a tourist location from it.

Assume S' to be the set of all tourist locations.
Lets talk about the first problem now. Assume a function f\_sum , such that:

f\_sum[i] = \sum_{j \in S'} D(i,j)

In order to calculate it we introduce another function f\_subtree where f\_subtree[i] tells us the number of tourist locations in the subtree of i.

We can calculate f\_sum[1] using DFS. For other nodes we can do another DFS and use the following relation

f\_sum[child] = f\_sum[parent] + (k - f\_subtree[child]) - f\_subtree[child]

This concludes with our problem one. Now moving on to the 2nd part of the problem.
Lets introduce another function f\_max such that

f\_max[i][0] = maximum \; distance \; of \; tourist \; location \; within \; subtree \; of \; i.
f\_max[i][1] = maximum \; distance \; of \; tourist \; location \; outside \; subtree \; of \; i.

Now we can run a DFS and for any node and its child, if f\_subtree[child] > 0 then

f\_max[node][0] = max(f\_max[node][0], f\_max[child][0] + 1)

Thus we would get first part of the function. For the 2nd part i.e to calculate f\_max[node][1], we run another DFS, where for any node and its child, let us take another set C which denotes all children of node other than child, then

f\_max[child][1] = max(f\_max[node][1], max(f\_max[c][1], where \; c \in C ))

Now that we solved both these problems individually, we can get back to our original problem. If we assume the required sum of distance for each node i is answer[i], then

Now we can loop through to find the maximum i with minimum value of answer[i].

TIME COMPLEXITY:

O(Nlog(N)) for each test case.

SOLUTION:

How is this O(N\log(N)) and not just O(N) ?

I feel like I did exactly the same thing but using a rerooting approach (compute the answer with the root at 1, then do a DFS to move the root and recompute the answer each time we move the root along an edge).

It passed samples but no test so I wonder whatâ€™s wrong, can someone tell ?
https://www.codechef.com/viewsolution/63344312
The code can look a bit big but is actually not so much, only the rerooting has 2 copy paste of 8-lines blocks.

Because you can use a multiset for computing the value of the farthest tourist attraction node distance, and insert and erase operations for a multiset take \mathcal{O}(\log N) time.

PS: We can do this in linear time as well by maintaining the parent contribution recursively.

Also there I think in the editorialistâ€™s a multiset should be used instead of a set to handle duplicates My Solution

But canâ€™t you do it recursively just storing the value of the farthest tourist for each node and taking max on children (see what I tried in my submission) ?

1
2 1
2
1 2


Thanks, I saw where the issue was with this and fixed it, but it still doesnâ€™t pass ^^
But nevertheless why do you think just using max values and updating recursively fail ?

It wonâ€™t fail if done correctly, I was just highlighting what the editorialistâ€™s solution did, I edited my previous post to clarify that.

Also, your latest submission fails for this.

1
4 2
2 3
1 4
3 2
2 4


Correct output is 3

Ok thanks for clarification.

Oh I see I did a very dumb mistake updating the answer only if the index was also bigger than previous answerâ€™s one. Still WA thoughâ€¦
I will try stress testing on my own thanks for the help.

Yeah, I edited the previous post, seems like test cases are weak as many solutions which fail this test case also got an AC.

Oh thatâ€™s bad x) Is the last one you submitted right so I can use it for stress testing ?

My O(n) solution : Solution: 63352377 | CodeChef. (If Anyone finds a failing test for it , please do reply to me )

Yes, Itâ€™s correct you can use this solution for stress testing.

Fails for this

1
3 2
1 2
2 1
1 3