树的重心

题目描述

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

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

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

样例

输入格式
第一行包含整数 n，表示树的结点数。

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

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

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10 ;

int h[N] , e[2 * N] , ne[2 * N] , idx ;    //注意初始化条件的图！！！！！！

bool st[N];                             

int n ;          

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

int res = N;                     // 记录最终最小的子节点数量

int dfs(int u)                  //返回包括u节点（u为根）在内的所有节点数量
{
    int better = 0 ;             //记录删除当前节点后连通块中点数的最大值
    int sum = 1 ;                //记录以当前节点为根的树的总点数
    st[u] = true ;               //标记当前节点已经被搜过
    for(int i = h[u] ; i != -1 ; i = ne[i])     
    {
        int j = e[i] ;
        if(!st[j])
        {
            int hh = dfs(j);       
            better = max(hh , better);
            sum += hh;
        }
    }
    better = max( better , n - sum);
    res = min( res , better );
    return sum ;
}


int main()
{
    memset( h , -1 ,sizeof h);
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++ )
    {
        int a , b ;
        cin >> a >> b ;
        add( a , b ) , add( b , a );
    }
    dfs(1);
    cout << res << endl;
    return 0 ;
}