题意简述
给出一棵无根树，求以那些节点为根时，与它直接相连的节点，它们的子树大小都相同。
思维路径
首先，显而易见的是，在 \(1 \le n \le 10^6\) 的数据范围下，我们不可能通过对每个节点作为根判断一次。因此，我们考虑选取一个节点为根计算全部。
我们作图来分析一下。
如上图，我们针对 \(2\) 号节点来做分析。首先我们默认以 \(1\) 号节点为根，与 \(2\) 号直接连接的有 \(1\) 号节点、\(3\) 号节点、\(4\) 号节点。
其中我们在遍历时，可以直接得到以 \(3\) 号节点为根的子树大小和以 \(4\) 号节点为根的子树大小。
紧接着，当 \(2\) 号节点为整个树的根时，形态如图所示。
可以发现，此时以 \(1\) 号节点为根的子树中有 \(1\) 号和 \(5\) 号两个节点，再回到第一张图，可以发现正是红圈圈出的部分，即除了 \(2\) 号节点为根的子树外的所有节点。
它的子树大小就是总节点个数 \(n\) 减去 \(2\) 号节点的子树大小。
推及所有节点在访问时，只需将其子树大小互相比较，再与 \(n\) 减去它本身的子树大小比较，全部相等即可记录答案。
实现细节
全程序的核心集中在 DFS 的遍历上。
注：主函数中默认根为 \(1\)，\(1\) 的父节点为 \(0\)。
首先我们定义两个变量。
int t=-1,ys=1;
其中 \(t\) 记录了子树大小，\(ys\) 表示子树是否全部相等，全部相等则为 \(1\)，否则则为 \(0\) 。
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
if(t==-1) t=sz[v];
else if(t!=sz[v]) ys=0;
}
紧接着是 DFS 的核心部分，\(sz\) 数组用来记录子树大小。
当 \(t\) 的值为 \(-1\) 时，说明这是第一棵被访问到的子树，因此记录子树大小。
否则就应进行比较，若不相等，设定 \(ys\) 值为 \(0\)，因为还要找其它节点是否符合，所以这里不能提前跳出。
sz[u]++;
if(t!=-1&&n-sz[u]!=t&&n-sz[u]!=0) ys=0;
if(ys) ans[++nA]=u;
最后在子树中增加自身，并判断除自己子树以外的情况。
此处 \(t\) 若等于 \(1\)，则说明改节点是叶子节点，没有子树，需跳过。
若 \(n\) 减去该子树大小与其他子树大小相同，说明符合条件，\(ys\) 的值也应保持为 \(0\)。
若 \(n\) 减去该子树大小恰好等于 \(0\)，说明这是 \(1\) 号节点，也需跳过。
最后记录答案。
根据题目输出格式中从小到大的整数，需要排序。
AC 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000009;
int n,sz[N],nE,hd[N],nA,ans[N];
struct edge{
int to,nxt;
} e[N<<1];
void add(int u,int v){
e[++nE]=(edge){v,hd[u]};
hd[u]=nE;
}
void input(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
}
void dfs(int u,int fa){
int t=-1,ys=1;
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
if(t==-1) t=sz[v];
else if(t!=sz[v]) ys=0;
}
sz[u]++;
if(t!=-1&&n-sz[u]!=t&&n-sz[u]!=0) ys=0;
if(ys) ans[++nA]=u;
}
void solve(){
dfs(1,0);
sort(ans+1,ans+nA+1);
for(int i=1;i<=nA;i++){
cout<<ans[i]<<" ";
}
}
int main(){
input();
solve();
return 0;
}