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 1 to n. If you cannot understand the concept of a tree here, please omit this problem.
Now we decide to colour its nodes with k distinct colours, labelled from 1 to k. Then for each colour i = 1, 2, · · · , k, define Ei as the minimum subset of edges connecting all nodes coloured by i. If there is no node of the tree coloured by a specified colour i, Ei will be empty.
Try to decide a colour scheme to maximize the size of E1 ∩ E2 · · · ∩ Ek, and output its size.
Input
The first line of input contains an integer T (1 ≤ T ≤ 1000), indicating the total number of test cases.
For each case, the first line contains two positive integers n which is the size of the tree and k (k ≤ 500) which is the number of colours. Each of the following n - 1 lines contains two integers x and y describing an edge between them. 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
Sample Output
1 0 1
题意：
有一棵N个点的无根树，以及K种颜色，先用这K种颜色染色。将连通相同颜色的点所需要的最少数量的边作为一个集合（其实也就类似于一种最小生成树），然后将所有颜色所形成的集合树做一个交集，现在要找到一种染色方案，使得这个交集最大。若不使用某种颜色，那么该颜色的边集为空集。
思路：
题意真的好难读懂呀！看了半天也没思路！我一开始往点的方向思考，实则不行，必须要往边的方向想才对。
在给某一种颜色染色时，最好是只染最外边的两个点，因为要省出一些点给其他颜色，有空集颜色出现肯定是不好的情况。对于每一条边，它的两点分别延伸出去两棵子树，所以只要看每一条边所对应的两棵子树大小，是否都大于等于K即可。若满足条件，则必在交集之中，最后深搜遍历就好了！
#include<bits/stdc++.h>
#define MAX 200005
using namespace std;
typedef long long ll;
int n,k,sum,num[MAX];
vector<int>ve[MAX];
void dfs(int u,int pre) //pre 表示上一个点
{
for(int i=;i<ve[u].size();i++)
{
int v=ve[u][i];
if(v!=pre) //为了使dfs不往回走
{
dfs(v,u); //先遍历至叶子结点
num[u]+=num[v]; //一层层结点数往上加
if(num[v]>=k&&n-num[v]>=k) //从尾部开始判断！！
sum++;
}
}
}
int main()
{
int i,T;
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n>>k;
for(i=;i<=n;i++)
{
ve[i].clear();
num[i]=;
}
for(i=;i<n;i++)
{
int x,y;
cin>>x>>y;
ve[x].push_back(y);
ve[y].push_back(x);
}
sum=;
dfs(,-);
cout<<sum<<endl;
}
return ;
}