植树
2025-02-04 13:46:01
发布于：上海
7阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
vector<int> tr[1000010];
int n;
vector<int> ans;
int dfs(int u,int fa){
int size = 1;//以u为根的子树大小
unordered_set<int> set;
for(int son:tr[u]){
if(son==fa)continue;
int son_sum = dfs(son,u);
size += son_sum;
set.insert(son_sum);
}
int top = n - size;
if(top>0)set.insert(top);
if(set.size()==1)ans.push_back(u);
return size;
}
int main(){
cin>>n;
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
tr[x].push_back(y);
tr[y].push_back(x);
}
dfs(1,-1);
sort(ans.begin(),ans.end());//动态数组从小到大排序
for(int x:ans)cout<<x<<" ";
return 0;
}
这里空空如也
有帮助，赞一个