直接看子树是否大于mx就行了。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; const int N=1e5+5; int head[N],next[N],go[N],mx; int tot=0; inline void add(int x,int y) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; } int vis[N],siz[N],ans[N]; inline void dfs(int x) { vis[x]=1; int i=head[x]; siz[x]=1; while (i) { int v=go[i]; if (!vis[v]) { dfs(v); siz[x]+=siz[v]; if (siz[v]>mx)ans[x]=0; } i=next[i]; } if (n-siz[x]>mx)ans[x]=0; } int main() { scanf("%d",&n); mx=n>>1; memset(ans,-1,sizeof(ans)); fo(i,1,n-1) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1); bool bz=0; fo(i,1,n) if (ans[i]!=0) { printf("%d\n",i); bz=1; } if (!bz)printf("NONE\n"); return 0; }