# King Killing CodeChef Solution | May Long Challenge | KKLING

Share:

king killing codechef solutionView 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.

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

• 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.

### C++

``````#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<long long> vec,data,leaves,ans;
void dfs1(long long now, long long last)
{
for(long long i=0; i<vec[now].size(); i++)
{
long long root= vec[now][i];
if(root!=last)
dfs1(root,now);
}
leaves.clear();
for(long long i=0; i<vec[now].size(); i++)
{
long long root= vec[now][i];
if(root!=last)
leaves.push_back(data[root]);
}
if(leaves.size()>0)
{
sort(leaves.begin(),leaves.end());
long long x=leaves,chk=0;
for(long long i=0; i<leaves.size(); i++)
{
if(leaves[i]!= x)
chk++;
}
if(chk==0)
data[now]+= x+1;
if(chk!=0)
data[now]+= x +2;
}
else
data[now]=0;
}
void dfs2(long long node, long long par, long long minh)
{
for(long long i=0; i<vec[node].size(); i++)
{
long long root= vec[node][i];
minh = min(minh,data[node]);
if(root!=par)
{
if(data[root]>=minh-1)
{
dfs2(root,node,minh);
}
}
}
if(data[node]==0)
{
ans.push_back(node);
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
long long t = 1; cin >> t;
while(t--)
{
long long N; cin >> N;
data.assign(N+1,0);
for(long long i=0;i<N-1; i++)
{
int l, r;
cin >> l >> r;
vec[l].pb(r), vec[r].pb(l);
}
dfs1(1,0);
int mn=INT_MAX;
for(long long i = 0; i<vec.size(); i++)
{
long long root = vec[i];
if(data[root]<mn)
{
mn = data[root];
}
}
for(long long i=0; i<vec.size(); i++)
{
long long root = vec[i];
if(data[root] == mn)
dfs2(root,1,mn);
}
sort(ans.begin(), ans.end());
cout<<ans.size()<<" "<<mn+1<<endl;
for (long long i = 0; i <ans.size(); ++i)
cout<<ans[i]<<" ";
cout<<endl;
for (long long i = 1; i <=N; ++i)
{
vec[i].clear();
}
data.clear();
ans.clear();
}
return 0;
}
``````

### Java

``````import java.util.*;
import java.io.*;

class KKLING{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
int[] from = new int[N-1], to = new int[N-1];
for(int i = 0; i< N-1; i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] tree = make(N, from, to);
int[] par = new int[N], d = new int[N];
int[] location = new int[N];//location of ith assassin, or -1 if i is not an assassin, or i is dead
int[] node = new int[N];//id of assassin on ith node, or -1 if no assassin on ith node
Arrays.fill(location, -1);
Arrays.fill(node, -1);
precalc(tree, par, d, location, 0, -1);
for(int i = 0; i< N; i++)if(location[i] != -1)node[location[i]] = i;

int[] set = java.util.stream.IntStream.range(0, N).toArray();//Maintaining sets of assassins

PriorityQueue<int[]> q = new PriorityQueue<>((int[] i1, int[] i2) -> {
if(d[i1] != d[i2])return Integer.compare(d[i1], d[i2]);
return Integer.compare(i1, i2);
});
for(int i = 0; i< N; i++)if(location[i] != -1)q.add(new int[]{i, i});
boolean[] processed = new boolean[N];

int winTime = -1;
for(int time = 1; time <= N; time++){
for(int[] pair:q){
location[pair] = -1;
node[pair] = -1;
}
//Min-heap to fetch assassin with location closest to root
PriorityQueue<int[]> nq = new PriorityQueue<>((int[] i1, int[] i2) -> {
if(d[i1] != d[i2])return Integer.compare(d[i1], d[i2]);
return Integer.compare(i1, i2);
});
//Moving to next[u], if u is location (par is eqivalent to next array)
//pair -> assassin ID
//pair -> location
q.clear();
//Merging assassins at same node
int prevAssassin = -1, prevNode = -2;
while(!nq.isEmpty()){
int[] pair = nq.poll();
if(pair == prevNode){
set[find(set, pair)] = find(set, prevAssassin);
}else {
prevNode = pair;
prevAssassin = pair;
location[pair] = pair;
node[pair] = pair;
}
}
//Checking if some assassin is at node 0 (0-based indexing)
if(node != -1){
winTime = time;
break;
}
//Processing all nodes having assassins in order of their depths
while(!q.isEmpty()){
int[] pair = q.poll();
process(nq, tree, processed, par, location, node, pair, par[pair], pair);
}
q = nq;
}
List<Integer> ans = new ArrayList<>();
for(int i = 0; i< N; i++)if(find(set, i) == find(set, node))ans.add(1+i);
pn(ans.size()+" "+winTime);
for(int x:ans)p(x+" ");pn("");
}
//Processing nodes
boolean process(PriorityQueue<int[]> q, int[][] tree, boolean[] processed, int[] par, int[] location, int[] node, int u, int p, int ancestor) throws Exception{
boolean contains = false;//Determining if there's any assassin in subtree of node u except at node u
for(int v:tree[u]){
if(v == p || processed[v])continue;
contains |= process(q, tree, processed, par, location, node, v, u, ancestor == -1?node[u]:ancestor);
processed[v] = true;
}
if(contains && node[u] != -1){
//Subtree of node u contains an assassin, so assassin at current node dies
location[node[u]] = -1;
node[u] = -1;
}
if(ancestor != -1 && node[u] != -1){
//Current assassn survived, and there's some ancestor killed on same day
//or node u itself, if no assassin in subtree of u
if(ancestor != node[u])par[u] = location[ancestor];
}
return contains || node[u] != -1;
}
void precalc(int[][] tree, int[] par, int[] d, int[] location, int u, int p){
par[u] = p;
location[u] = u;
for(int v:tree[u])if(v != p){
location[u] = -1;
d[v] = d[u]+1;
precalc(tree, par, d, location, v, u);
}
}
int[][] make(int N, int[] from, int[] to){
int[] cnt = new int[N];
for(int x:from)cnt[x]++;
for(int x:to)cnt[x]++;
int[][] g = new int[N][];
for(int i = 0; i< N; i++)g[i] = new int[cnt[i]];
for(int i = 0; i< N-1; i++){
g[from[i]][--cnt[from[i]]] = to[i];
g[to[i]][--cnt[to[i]]] = from[i];
}
return g;
}
int find(int[] set, int u){return set[u] == u?u:find(set, set[u]);}
static void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
//        new KKLING().run();
new Thread(null, new Runnable() {public void run(){try{new KKLING().run();}catch(Exception e){e.printStackTrace();System.exit(1);}}}, "1", 1 << 28).start();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}``````

### Python

``````from collections import defaultdict
import sys
sys.setrecursionlimit(2000000)
dp = []
global dp
flag = 0
temp = set()
mini = float("inf")
if i!=parent:
flag += 1
mini = min(mini,ans)

if flag == 0:
dp[curr] = 0
return dp[curr]
if len(temp) == 1:
dp[curr] = temp.pop()+1
elif curr == 1:
dp[curr] = mini+1
else:
dp[curr] = mini+2
return dp[curr]

if search==0 and dp[curr] == 0:
return
if parent == 0 or search==dp[curr]:
search = dp[curr]-1
if parent==0:
if dp[i]==search:
else:
if i!=parent and dp[i]>=search:

t = int(input())
for _ in range(t):

n = int(input())
dp = [-1]*(n+1)