Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit:262144/262144 K (Java/Others)
Total Submission(s): 19 Accepted Submission(s): 10
Problem Description
Consider a un-rooted tree T which is not the biological significance of tree or plant,but a tree as an undirected graph in graph theory with n nodes, labelled from 1to n. If you cannot understand the concept of a tree here, please omit thisproblem.
Now we decide to colour its nodes with k distinct colours, labelled from 1 tok. Then for each colour i = 1, 2, · · · , k, define Ei as the minimum subset ofedges connecting all nodes coloured by i. If there is no node of the treecoloured by a specified colour i, Ei will be empty.
Try to decide a colour scheme to maximize the size of E1 ∩ E2 · · · ∩ Ek, andoutput its size.
Input
The first line of input contains an integer T (1 ≤ T ≤ 1000), indicating the totalnumber of test cases.
For each case, the first line contains two positive integers n which is thesize of the tree and k (k ≤ 500) which is the number of colours. Each of thefollowing n – 1 lines contains two integers x and y describing an edge betweenthem. We are sure that the given graph is a tree.
The summation of n in input is smaller than or equal to 200000.
Output
For each test case, output the maximum size of E1 ∩ E1 … ∩ Ek.
Sample Input
3
4 2
1 2
2 3
3 4
4 2
1 2
1 3
1 4
6 3
1 2
2 3
3 4
3 5
6 2
Sample Output
1
0
1
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<set>
using namespace std;
const int maxn = 200000 + 10;
int vis[maxn];
vector<int>v[maxn];
int ans,n,k;
void dfs(int x, int pre)
{
vis[x] = 1;
for (int i = 0; i < v[x].size(); i++)
{
int temp = v[x][i];
if (temp == pre)continue;
dfs(temp, x);
vis[x] += vis[temp];
if (vis[temp] >= k&&n – vis[temp] >= k)ans++;
}
}
int main()
{
int T;
int a,b;
scanf(“%d”, &T);
while (T–)
{
memset(vis, 0, sizeof(vis));
ans = 0;
scanf(“%d%d”, &n, &k);
for (int i = 1; i <= n; i++)
{
v[i].clear();
}
for (int i = 1; i < n; i++)
{
scanf(“%d%d”, &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1, -1);
printf(“%d\n”, ans);
}
return 0;
}