切割树 无根树转为有根树

原题：1325

题意：

给一个无根树，输出所有点，满足删了这个点后剩下各个部分结点数不超过n/2

解析：

知道转变成有根树的话，问题就直接解决了

首先用set<int>son[i]存与i连接的结点，而且因为无根树的随便一个结点都可以当root，我们便选择第一个输入的作为root

对于每个father，把所有儿子的set里面的出现的father删除，那么son的意义就从连接点变成了儿子集合了。 *如果需要确定father，可以在这个时候确定

变成了有根树，那么接下来只要类似dfs一遍，就可以得到一个结点所在子树的结点数了

代码：

#include<iostream>
#include<stdio.h>
#include<set>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int n,root;
set<int>son[10009];
int val[10009];
void build(int ro){
for(set<int>::iterator it=son[ro].begin();it!=son[ro].end();it++){
int so=*it;
if(son[so].find(ro)!=son[so].end())son[so].erase(ro);
build(so);
}
}
int count(int ro){
int ans=1;
for(set<int>::iterator it=son[ro].begin();it!=son[ro].end();it++){
ans+=val[*it]=count(*it);
}
return ans;
}
int main(){
cin>>n;
if(n==1){
printf("1n");return 0;
}
for(int i=1;i<n;i++){
int a,b;scanf("%d%d",&a,&b);
if(i==1)root=a;
son[a].insert(b);
son[b].insert(a);
}
build(root);
val[root]=count(root);
int op=n/2;
for(int i=1;i<=n;i++){
if(i==root){
int f=1;
for(set<int>::iterator it=son[i].begin();it!=son[i].end();it++){
if(val[*(it)]>op){f=0;break;}
}
if(f)printf("%dn",i);
}else{
int f=1;
if(val[root]-val[i]>op)f=0;
for(set<int>::iterator it=son[i].begin();it!=son[i].end();it++){
if(val[*(it)]>op){f=0;break;}
}
if(f)printf("%dn",i);
}
}
}
/*
10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8
*/

最后

以上就是凶狠宝马为你收集整理的切割树 无根树转为有根树的全部内容，希望文章能够帮你解决切割树 无根树转为有根树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。