题解 P6591 【[YsOI2020]植树】

简易树上操作。题目没有给根那干脆就以$1$号点为根嘛。一遍dfs处理出每个节点作为根节点子树的大小，然后直接一个一个点判断即可。可以用大减小来判断上方子树的大小。 $code:$ ``` #include<cstdio> const int MX=1000003; int fir[MX],fa[MX],sz[MX];struct STR{int to,nxt;}edge[MX<<1]; void add(int u,int v,int pos){ edge[pos].to=v;edge[pos].nxt=fir[u];fir[u]=pos; } void dfs(int now){ sz[now]=1; for(int i=fir[now];i;i=edge[i].nxt){ int qck=edge[i].to;if(fa[now]==qck)continue;fa[qck]=now;dfs(qck);sz[now]+=sz[qck]; } } bool ok(int now){ int ask=(now-1?sz[1]-sz[now]:sz[edge[fir[now]].to]); for(int i=fir[now];i;i=edge[i].nxt){ int qck=edge[i].to;if(fa[now]==qck)continue;if(sz[qck]!=ask)return 0; } return 1; } void qin(int &x){ x=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-48;c=getchar();} } void qout(int x){ if(x>9)qout(x/10);putchar(x%10+48); } int main(){ int n;qin(n); for(int i=1;i<n;i++){ int u,v;qin(u);qin(v);add(u,v,i);add(v,u,n-1+i); } dfs(1);for(int i=1;i<=n;i++)if(ok(i)){qout(i);putchar(' ');} return 0; } ```