切割树无根树转为有根树

116 阅读 0 评论 77 点赞

我是靠谱客的博主凶狠宝马，这篇文章主要介绍切割树无根树转为有根树，现在分享给大家，希望可以做个参考。

原题：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
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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
*/