树的重心
定义:重心是指树中的一个节点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心
性质:树中所有节点到重心的距离之和最小,如果有俩个重心,那么他们距离之和相等
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx, n,ans=N,L;
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u)
{
int res = 0;//删除某个节点之后,最大的连通子图节点数
int sum = 1;//存储以u为根的树的节点数,包括u
st[u] = true;//存访问过u节点
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
int s = dfs(j);//u节点的单颗子树节点数
res = max(res, s);//记录最大连通子图的节点数
sum += s;//以j为根的树的节点数
}
}
res = max(res, n - sum);//选择u节点为重心,最大的连通子图节点数
if (res < ans)
{
L = u;//存真重心
ans = res;//存遍历过假设重心中,最小的最大连通子图的节点数
}
return sum;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
//重心对应的最大连通子图节点数
cout << ans << endl;
//重心
cout << L << endl;
return 0;
}