算法板子：树形DP、树的DFS——树的重心

思想：

代码：

#include <iostream>
#include <cstring>
using namespace std;const int N = 1e5 + 10;// vis标记当前节点是否被访问过; vis[1]=true代表编号为1的节点被访问过
bool vis[N];
// h数组为邻接表; h数组上的每个坑位都串了一个单链表; h[1]=3代表编号为1的节点的第一个邻接节点的编号为3
// e[i]代表编号为i的节点的值; ne[i]代表编号为i的节点的下一个节点的编号; idx代表当前可用编号; 注意这里的e和ne数组要开2*N的大小
int h[N], e[2 * N], ne[2 * N], idx;// res存储去掉各个节点后的最大连通块的最小值; 初始记录为最大值，最大值为最大连通块的点数，就是树中所有的节点数
int n, res = N;// 值为a的节点和值为b的节点之间存在一条边，在以a打头的单链表上插入头结点b
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}// 得到以u为根的树的总节点数
int dfs(int u)
{vis[u] = true; // 标记u节点已经访问过int size = 0; // 代表以u为根的最大子树的节点数; 初始时最大子树节点数为0int sum = 1; // 代表以u为根的树的总节点数; 初始时该树的总节点数为1// 遍历u节点的邻居; 也就是遍历u的每个儿子for (int i = h[u]; i != -1; i = ne[i]){int j = e[i]; // 得到u节点的邻居节点，也就是u的儿子if (vis[j]) continue; //避免叶子结点找到的邻居节点为父节点int s = dfs(j); // 得到以某个儿子节点为根的树的总节点数; 也就是某个子树的节点数size = max(size, s); // 更新最大子树节点数sum += s; // 累加所有子树的节点数}// 如果删掉了u这个点，那么整个树可以分成两部分，u的所有子树和u的上面的剩余部分// u的所有子树的最大节点数为size，剩余部分为整棵树的总节点数减去以u为根的树的节点数，求max后得到删去u后连通块中的最大节点数// 再和删去其他节点的答案作比较，更新最小的最大连通块的点数res = min(res, max(size, n - sum));return sum;
}int main()
{cin >> n;// 首先要初始化邻接表hmemset(h, -1, sizeof h);// 将输入的点构成邻接表for (int i = 0; i < n - 1; i ++ ){int a, b;cin >> a >> b;// 比如a=1 b=3，代表值为1的节点和值为3的节点之间存在边; 那么1的单链表后面要串个3，3的单链表后面要串个1add(a, b); add(b, a);}// 从树中的任意一个节点开始dfs都可以; 比如也可以是dfs(n-1)dfs(1);cout << res << endl;return 0;
}