题目描述

给定一颗树，树中包含 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

思路分析

树的深度优先遍历dfs(u)最大的好处:在遍历过程中可以算出以u为根节点的树中结点的数量.
在计算与遍历过程中可”顺便”完成其他工作,因此演变出了各种各样树的算法题. 模板如下:

  int dfs(int u)
  {
    st[u] = true;  //st[u]表示点u已经被遍历过

     for (int i = h[u]; i != -1; i = ne[i])
     {
        int j = e[i];
        if (!st[j]) dfs(j);
     }
   }

本题要求:输出将重心删除后,剩余各个连通块中点数的最大值.
本题思路:对树中的每个点都求出:把这个点删掉之后,其余所有连通块的点数的最大值,以打擂台的方式求出其中最小的那一个

各个变量意义:

sum表示以这一点为根结点的树中所有结点个数
res表示删除这一点后的连通块中结点数目的最大值(不断更新)
ans表示所有(依次删除每个结点的情况)最大连通结点数目的最小值,即各个res的最小值(不断更新)
所有备注可结合上方图示一起看

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=100010,M=N*2;      // 无向图,邻接表指针2*(n-1)故令M为2N
int n;                        
int h[N],e[M],ne[M],idx,ans=N; // h[]存储邻接表各个头结点,此处e[],ne[],idx同单链表
bool stl[N];    // 标记当前这个结点是否已访问,作用:使遍历不走回头路,防止子节点搜索父节点
// head, e[M],ne[M],idx; 是一条单链表
// h[N], e[M],ne[M],idx; 是N条单链表组成邻接表
void add(int a,int b)  // 头插法
{   // e记录当前点的值,ne下一点的地址,h记录指向的第一个点的地址,idx:当前用到了哪个结点(的下标)
    e[idx]=b;
    ne[idx]=h[a];            
    h[a]=idx;
    idx++;
}

int dfs(int u)      // 返回以u为根的树中所有结点个数(存在变量sum中)
{
    int res=0,sum=1;            // res存储当前连通块中结点的最大数目
    stl[u]=true;                // 走过是true没走过是false

    for(int i=h[u];i!=-1;i=ne[i]) // 从u为表头的链表开始遍历,中间递归走各个分叉,直到u的链表尾结束
    {
        int j=e[i];                 
        if(stl[j]==false)           // 只有这一点没走过才走这一点所在的分叉
        {
            int s=dfs(j);           // s为中间变量,存储u的各个子树的结点数目
            res=max(res,s);         // 通过打擂台获得删除u后u子树中最大连通块的结点个数(图中6与3-9比谁结点多)
            sum=sum+s;              // 以u为根结点的树结点数量=1+它各个子树的结点数量
        }
    }
    res=max(res,n-sum);  // 比较删除u后的u子树中最大的连通块(6,3-9中的更大者),和整个树减u子树剩下的连通块(1-2-8-5-7)
    ans=min(res,ans);           // 在所有最大的连通块结点数目找到最小值
    return sum;                 // 返回以u为根的子树结点的个数(1+u的所有子树结点个数)
}

int main()
{
    memset(h,-1,sizeof h);      // 将h[]数组初始化成-1,-1表示空结点
    scanf("%d",&n);                 
    for(int i=0;i<n-1;i++)      // n个结点插n-1次构成树
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);       // 无向图a→b且b→a
    }
    dfs(1);                      // 可从树中任意一个点开始遍历

    printf("%d",ans);            // 输出所有最大的连通块结点数目中的最小值

    return 0;
}