题目

---

解题思路

利用树的深度遍历
对每个结点，算出删除它之后的各个连通块的最大结点数是多少
然后算出其中最小的
详细思路见代码注释

---

代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入，n个节点
int ans = N; //表示重心的所有的子树中，最大的子树的结点数目bool st[N]; //记录节点是否被访问过，访问过则标记为true//a所对应的单链表中插入b  a作为根 
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}//返回以u为根的子树中节点的个数，包括u节点，便于计算连通块的结点个数
int dfs(int u) 
{int res = 0; //存储 删掉某个节点之后，各连通子图中最大的连通子图节点数st[u] = true; //标记访问过u节点int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点//访问u的每个子节点for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];//因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过if (!st[j]) {int s = dfs(j);  // u节点的单棵以一个子节点为根的子树的节点数 如图中的size值 也即其作为把u删了以后的联通子块的结点数res = max(res, s); // 记录以u的每个子节点为根的联通子块中最大联通子图的节点数sum += s; //以j为根的树 的节点数}}//n-sum 如图中的n-size值，不包括根节点4；res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数  其实是拿子节点的形成的最大的，与它上面的整体比ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数return sum;
}int main() {memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点cin >> n; //表示树的结点数// 题目接下来会输入，n-1行数据，// 树中是不存在环的，对于有n个节点的树，必定是n-1条边for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b;add(a, b), add(b, a); //无向图}dfs(1); //可以任意选定一个节点开始 u<=ncout << ans << endl;return 0;
}
作者：松鼠爱葡萄
链接：https://www.acwing.com/solution/content/13513/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。