题目描述

树的重心（树与图的深度优先遍历）和点的数量线性相关（O(n+m)）

连通块
连通块有两种：各个子树，父节点所在的连通块，
父节点所在连通块中点的数量，就是总数减去当前整棵子树的节点数
各个子树中的节点数量，就是子节点dfs的返回值

树是图的一种
树的重心不一定只有一个

深度优先遍历，每读一个点相当于往下多了一层（竖着搜索）需要回溯
每个点只能遍历一次（所以要开一个bool数组st[N]）
利用单链表将数字连起来
可以求出每棵子树点的数量，剩下的最大的那个就是原来点的数量减去子树点的数量也就是最大值

宽度优先搜索：已确定一个点，这个点可以往下读的每一个点构成一层（横着搜索）

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=N*2;

int n;
int h[N];   //头结点
int e[M];   //存数值
int ne[M];  //存next指针
int idx;    //节点序号
bool st[N];   //这个点有没有遍历过（每个点只能遍历一次）

int ans=N;  //存最小最大值

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

//返回以u为根节点的子树中点的数量
int dfs(int u)
{
    st[u]=true;  //表示已经被搜索过了

    int sum=1;//当前子树的大小    （包含了被当作重心的点）
    int res=0;//将该点删去后，剩下连通块的最大值
    for(int i=h[u];i!=-1;i=ne[i])    //-1表示节点最后了
    {
        int j=e[i];       //要遍历的数字
        if(!st[j]) 
        {
            int s=dfs(j);  //如果这个点没有遍历过，则从他开始遍历,s为该点子树的大小（包含了根节点）
            res=max(res,s);
            sum+=s;//以j为根节点的子树是以u为根节点的子树的一部分
        }
    }

    res=max(res,n-sum);
    ans=min(ans,res);
    return sum;//返回树的大小
}
int main()
{
    cin>>n;

    memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);    //无向图（双向奔赴）
    }


    dfs(1);   //随便找一个点开始遍历（将图转化成树）

    cout<<ans<<endl;

    return 0;
}