HDU 6228/2017ACM/ICPC 沈阳 Tree 【DFS】
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
【题意】
给出一棵有n个节点的树,现在你可以用k种颜色对节点染色,每种颜色对应一个集合,表示将树上所有这种颜色的点连起来经过的最小边。现在需要求所有集合取交集后的大小。
【思路】
假设我们取定1为根节点。
显然要是结果最大,相同颜色应该要尽可能分布在树的顶部和底部。
虽然我们需要考虑的是边,但是我们可以转化为对每个节点去考虑。令在这个节点的两侧每种颜色均有分布,那么一定会有一条公共边。
先用DFS求出每个点的子孙节点个数(包括自身),假设为x,那么它的上面点的个数为n-x,只要x>=k&&(n-x)>=k即能满足上面的条件。
我们只要枚举每个点,满足条件点的个数即为答案。
#include <cstdio>
#include <cmath>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
typedef long long ll;
const int maxn = 200005;
const ll mod = 10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
int n,k,ans;
int num[maxn];
vector<int>vec[maxn];
void dfs(int u,int pre)
{
num[u]=1;
for(int i=0;i<vec[u].size();i++)
{
int v=vec[u][i];
if(v==pre) continue;
dfs(v,u);
num[u]+=num[v];
if(num[v]>=k&&n-num[v]>=k) ans++;
}
}
int main()
{
int u,v;
rush()
{
mst(num,0);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
vec[i].clear();
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
}
ans=0;
dfs(1,-1);
printf("%d\n",ans);
}
return 0;
}
上一篇: 【HDU6228】【2017ACM/ICPC亚洲区沈阳站】Tree
下一篇: 后序中序求层序