CodeChef: May Long Challenge | King Killing | KKLING | Solution

Codechef

View on Codechef

In a faraway kingdom there are NN cities numbered 11 to NN connected to each other in the form of a tree. The city numbered 11 is the kingdom where the king resides. A city is called a leaf if it is not the kingdom and it has exactly one adjacent city. Each leaf city has an assassin.

The enemies of the king have announced a huge reward for the assassination of the king. Each assassin starts moving from his current city following the shortest path to the kingdom. It takes exactly 11 day for an assassin to move to an adjacent city..

The assassins don’t want to split the reward, so if an assassin AA encounters any other assassin BB ahead of him on the same path that AA is supposed to follow (no matter how far ahead), then AA uses his magical power to attack BB.

After all the magical powers were used, every assassin who was attacked dies. Suppose AA is a living assassin who attacked somebody. Now, AA will move directly to the position of the assassin closest to the kingdom that AA attacked, with the cost of 11 day. If there are multiple assassins in the same city simultaneously, they form a pact not to kill each other and start moving together. Once an assassin reaches the kingdom, he cannot be killed anymore, since he can kill the king, take the reward, and leave.

Your task is to find which assassin will reach the kingdom first and in how many days. If more than one assassin reaches the kingdom simultaneously, output all of them in sorted order. Each assassin is represented by the number of the city where they started from.

Input

  • The first line contains an integer TT, the number of test cases
  • The first line of every test case contains a single integer NN, the number of cities.
  • Each of the next N−1N−1 lines contains two integers uu and vv denoting that city uu is connected to city vv.

Output

  • For every test case, the first line should contain KK and TT, the number of assassins who are first to reach and the number of days required.
  • In the next line print KK space-separated integers denoting the assassins who are first to reach the kingdom in sorted order.

Constraints

  • 1≤T≤1051≤T≤105
  • 3≤N≤2⋅1053≤N≤2⋅105
  • 1≤u,v≤N1≤u,v≤N
  • The sum of NN over all test cases does not exceed 106106
  • The connections form a tree structure.

Subtasks

Subtask #1 (30 points):

  • T≤103T≤103
  • N≤2⋅103N≤2⋅103
  • Sum of NN over all test cases ≤104≤104
  • Time limit: 11 sec

Subtask #2 (70 points):

  • Original Constraints
  • Time limit: 22 sec

Sample Input

2
10    
1 2
1 3
2 4
2 5
3 6
3 7
5 8
6 9   
6 10
7
1 2
2 3
2 4
4 5
4 6
5 7

Sample Output

3 3
8 9 10
1 3
7




Explanation

Test Case 1 :

The assassins are initially present at nodes 44, 77, 88, 99, and 1010 (consider it day 00). On day 11, their positions become:

  • Assassin 44 => Node 22
  • Assassin 77 => Node 33
  • Assassin 88 => Node 55
  • Assassin 99 => Node 66
  • Assassin 1010 => Node 66

Now, since Assassin 44 is in the same path as assassin 88, and assassin 77 is in the same path as assassin 99 and assassin 1010, they both will be assassinated and assassin 88 will get to reach node 22 at cost of 11 day (no benefit) and assassin 99 and 1010 will also reach node 33 in one day (which is Day 22). Now assassin 88 is on node 22 and assassin 99 and 1010 are at node 33, all three of them reach node 11 simultaneously so all three of assassin 88, assassin 99 and assassin 1010 win (With a total cost of 33 days).

Test Case 2 :

The assassins are initially present at node 33, 66, and 77 on day 00. On day 11, their position becomes :

  • Assassin 33 => Node 22
  • Assassin 66 => Node 44
  • Assassin 77 => Node 55

Now since Assassin 33 and assassin 66 are on the path of assassin 77, the assassin 77 will kill both of them and will advance to the position of assassin 33, that is node 22 (nearest position to the kingdom), and this will cost him 11 day. On the next day (day 33), he will reach the kingdom and take the reward.

Solution will be updated here soon. Keep tracking

See more posts here

Leave a Comment

Your email address will not be published. Required fields are marked *

x