# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Dhananjay Raghuwanshi

Tester: Felipe Mota, Abhinav Sharma

Editorialist: Pratiyush Mishra

# DIFFICULTY:

2859

# PREREQUISITES:

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:

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

This concludes with our problem one. Now moving on to the 2nd part of the problem.

Lets introduce another function f\_max such that

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

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

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:

Editorialistâ€™s Solution

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution