首先我们先要了解什么是树的重心

树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点1后，树将分成两个连通块：$(2,4,5)$，$(3,6,7)$，则最大的连通块包含节点个数为3。若去掉点2，则树将分成3个部分，$(4)$，$(5)$，$(1,3,6,7)$最大的连通块包含4个节点；第一种方法可以得到更小的最大联通分量。可以发现，其他方案不可能得到比3更小的值了。所以，点1是树的重心。

树的重心的一些性质：

删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心，且相邻；树中所有节点到重心的距离之和最小，如果有两个重心，那么它们距离之和相等；两个树通过一条边合并，新的重心在原树两个重心的路径上；树删除或添加一个叶子节点，重心最多只移动一条边。

分析

任选一个节点为根，把无根树变成有根树，然后dp[i]表示以i为根的子树的节点个数。不难发现：

那么假设i是重心，在删除i之后$max(dp[j])(j\in Son(i))$还要与i上面的所有节点(可看成一棵子树)比，也就是n-dp[i]。右图中我们假设2号节点是重心，那么除了他们儿子节点为根的子树4和5以外，还有1367节点也可看成一棵子树，所以$f[i]=max(max(dp[j]),n-dp[i])$

(f[i]就是以i为重心的最大子树节点数)，那么答案就是$min(f[i])(i\in (1n))$

搜索时，还是递归到底层，回溯时进行累加，再利用重心的性质，所有子树的节点数不超过总节点数的$1/2$，更新flag的值，就可以找到重心节点了。

代码

先以1为根节点，构造一棵树

#include <cstdio> #include <vector> using namespace std; const int MAXN = 1e5 + 5; vector<int> a[MAXN], v[MAXN]; int de[MAXN], fa[MAXN], dp[MAXN], f[MAXN]; bool vis[MAXN], flag[MAXN]; int n, m, ans; void Find_Son(int); void Find_Father(int); void dfs(int, int); void Init(); void Read(); void DP(int); int main() { Read(); Init(); DP(1); for(int i = 1; i <= n; i++) if(flag[i]) ans++; printf("%d\n", ans); for(int i = 1; i <= n; i++) if(flag[i]) printf("%d\n", i); return 0; } void Find_Son(int now) { for(int i = 0; i < a[now].size(); i++) { if(!vis[a[now][i]]) { v[now].push_back(a[now][i]); vis[a[now][i]] = 1; Find_Son(a[now][i]); } } } void Find_Father(int now) { for(int i = 0; i < v[now].size(); i++) { fa[v[now][i]] = now; Find_Father(v[now][i]); } } void dfs(int now, int step) { de[now] = step; for(int i = 0; i < v[now].size(); i++) dfs(v[now][i], step + 1); } void Init() { vis[1] = 1; Find_Son(1); fa[1] = 1; Find_Father(1); dfs(1, 1); } void Read() { int A, B; scanf("%d", &n); for(int i = 1; i < n; i++) { scanf("%d %d", &A, &B); a[B].push_back(A); a[A].push_back(B); } for(int i = 1; i <= n; i++) flag[i] = 1; } void DP(int now) { dp[now] = 1; for(int i = 0; i < v[now].size(); i++) { DP(v[now][i]); dp[now] += dp[v[now][i]]; if(dp[v[now][i]] > n / 2) flag[now] = 0; } if(n - dp[now] > n / 2) flag[now] = 0; }