前置知识：树的重心

此题呢是可以 $n$ 次 dfs，以 $\text O(n^2)$ 的时间复杂度求解的。

但，这只是常规做法。

众所周知，树的重心可以以一次 dfs 以玄妙的方式求解以一个节点为根的最大子树大小。

这不是这道题需要去比较的吗？

我们把以一个节点为根的最大子树大小存在一个数组里面，再以一个循环比较输出就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int head[10010],to[20010],nxt[20010],tot;
void add(int u,int v){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
int dp[10010],siz[10010];
void dfs(int x,int fa){
	siz[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		if(to[i]==fa) continue;
		dfs(to[i],x);
		siz[x]+=siz[to[i]];
		dp[x]=max(dp[x],siz[to[i]]);
	}
	dp[x]=max(dp[x],n-siz[x]);
}
int main() {
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v),add(v,u);
	}
	dfs(1,0);
	int mid=n>>1,cnt=0;
	for(int i=1;i<=n;i++)
		if(dp[i]<=mid)
			cnt++,cout<<i<<"\n";
	if(!cnt) cout<<"NONE";
	return 0;
}