本文共 619 字，大约阅读时间需要 2 分钟。

问题引入

对于一棵$n$个节点的无根树，找到一个点，使得把该树变成以该点为根的有根树时，最大子树的节点数最小（删除这个点后的最大连通块最小）

设$d(i)$为以$i$为根节点的子树个数，则：

$d(i)=\Sigma d(j)+1$

若节点$i$的子节点为$v$，那么最后的答案就是使$max(d(v),n-d(i))$最小的节点$i$

代码

vector
   
     G[maxn];int d[maxn];int n, ans = inf, id;int dfs(int u, int father) {     //dfs(1,-1)    d[u] = 1;    for (auto v: G[u]) {           if (v != father) d[u] += dfs(v, u);    }    int res = n - d[u];    for (auto v: G[u]) {           if (v != father) res = max(res, d[v]);    }    if (ans > res) ans = res, id = u;    return d[u];}