AcWing 846. 树的重心
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数n，表示树的结点数。
接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。
输出格式
输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。
数据范围
输入样例
9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6
输出样例：
4
代码
#include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair PII; const int N = 1e5 + 10; int ans = 0x3f3f3f3f; int n; vectorvec[N]; int vis[N]; int dfs(int now) { vis[now] = 1; int sum = 1, res = 0; //res 剩余连通块中点数的最大值 //sum 当前节点的子树点数再加上自己的点数 for (int i = 0;i < vec[now].size();++i) { if (!vis[vec[now][i]]) { int s = dfs(vec[now][i]);//一个子树的大小 res = max(res, s);//所有子树大小的最大值 sum += s; //所有子树再加上根节点的大小 } } res = max(n - sum, res);//父节点子树大小 ans = min(ans, res); // 最大子树的最小值 return sum; } int main() { cin >> n; for (int i = 0;i < n - 1;++i) { int u, v; cin >> u >> v; vec[u].push_back(v); vec[v].push_back(u); } dfs(1); cout << ans << endl; }
