题目描述

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围
1≤n≤105

样例

输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4

看代码即可

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010,M=N*2;
int n;
int h[N],e[M],ne[M],idx;//h表示根节点，e表示节点的值是多少，所有节点都用一个值来表示（即idx)
//ne表示next指针 
bool st[N];//st用来来根据idx表示的下标判断是否访问过 
int ans=N;//记录全局的连通块中点数的最大值 
void add(int x,int b)
{
    e[idx]=b,ne[idx]=h[x],h[x]=idx++;
}
//返回以u为根的子树中 点的数量 
int  dfs(int u)
{
    st[u]=1;
    //每次搜索时都假设这个点是重心，然后用res记录删掉这个点之后连通块点数的最大值
    //在用ans记录所有重心的联通块的点数的最小值 
    int sum=1,res=0;//sun记录以u为根节点的点的个数，因为根节点也算所以从1开始
    //res记录把这个根节点去掉后每个连通块的点的数量的最大值 
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];//j表示某个节点的值，可以表示这个节点 
        if(!st[j])//将每个节点变成下标来判断某个节点是否被访问过 
        {
            int s=dfs(j);//s表示此根节点每个子节点的点的个数 
            res=max(res,s);//因为根节点的每个子节点数也算连通块，所以当这个根节点去掉之后每个子节点
            //需要跟res比较一下 
            sum+=s;//记录每个以j为根节点的点的个数 
        }
    }
    res=max(res,n-sum);//选择以u节点为重心，最大的连通子图节点数（可以看一下y总的图）
    //n-sum表示删掉以u为根节点之后非u子节点的剩余节点的个数 
    ans=min(ans,res);//ans表示遍历过的每个根节点（假设每个根节点都是重心）中
    //最小的最大联通子图的 节点数
    return sum;//返回每个以u为根节点的点的个数 
}
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;
    return 0;
}