植树
2025-02-04 13:46:01
发布于：上海
18阅读
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;
}
全部评论 1
这个可以过
#include<iostream> #include<vector> using namespace std; const int N = 1e6 + 9; vector<int> tree[N];//邻接表 int ch[N];//以cur为根的子树的所有节点数量 int n;//节点数量 void dfs(int u, int fa){//u为当前节点，fa为父节点 //因为当u当根节点时候，如果父节点不是-1，那么-1 ch[u] = tree[u].size() - (fa != -1); for(int v : tree[u]){//遍历u的子节点 if(v == fa) continue; dfs(v, u); } ch[fa] += ch[u];//将u的子节点数量加到父节点上 } int main(){ cin >> n; for(int i = 1; i < n; ++i){ int x, y; cin >> x >> y; tree[x].push_back(y); tree[y].push_back(x); } dfs(1, -1); //for(int i = 1; i <= n; ++i) cout << ch[i] << " "; bool flag = 1;//首先判断根节点是否平衡 for(int i : tree[1]){//遍历根节点的子节点 if(ch[i] != ch[tree[1][0]]){//如果子树大小数量不同 flag = 0;break; } } if(flag == 1) cout << 1 << " ";//如果根节点下单子树大小相同，则输出根节点 for(int i = 1; i <= n; ++i){ //如果子树大小为0，说明这个点原先是叶子节点只链接了一个父节点 //n-1-子树大小，将当前节点的子树大小和 n - 1 -ch[i]就可以得出另外一边的子树的总和 if(ch[i] == 0 || ch[i] == n - 1 - ch[i]) cout << i << " "; } return 0; }2026-02-25 来自 浙江
0
有帮助，赞一个