AcWing 846. 树的重心(对于全过程每一个状态的注释)
原题链接
简单
作者:
ACkingyk
,
2023-11-18 18:22:52
,
所有人可见
,
阅读 53
个人理解
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;//结点数量
const int M = 2*N;//边的数量
int idx;//作为边的序号
int h[N],e[M],ne[M];
bool st[N];//状态标记
int n,ans =N;
void add(int a,int b)//表示a指向b
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int dfs(int u)//
{
int res = 0;//res表示删除u结点后最大的联通块中结点总数
int sum = 1;//算出u作为根节点的树的结点总数
st[u] = true; //标记这个结点走过了
for(int i = h[u];i!=-1;i=ne[i])//向下随机选择一个u的儿子结点
{
int j = e[i];//找出i代表的序号
//如果这个结点没有走过
if(!st[j])
{
int s = dfs(j);//s表示u结点的某一个孩子的结点总数
res = max(res,s);//在这里可以比较出u的所有子树作为连通块最大的那一个
sum += s;//计算出u结点作为根节点的树的节点总数
}
}
//现在res表示的是u的所有孩子作为最大连通块中最大的那一部分
//但是没有考虑把u和它的孩子全部删去那一个连通块的节点总数
res = max(res,n-sum);
//由于ans表示的是所有最大中的最小,res作为某一个结点删去的最大值
//所以用min
ans = min(ans,res);
return sum;
}
int main()
{
cin >> n;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
int a,b;
cin >> a >> b;
add(a,b),add(b,a);
}
dfs(1);//从任意一个结点遍历都可以
cout << ans;
}