acwing 846 树的重心

#include
#include
using namespace std ;
const int N = 1e5 + 10 ;
int n ;
int h[N] , e[2*N] , idx ,  ne[2 * N] ;
int ans = N ;
bool st[N] ;
void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
int dfs(int u)
{
    int count = 1 , res = 0 ;
    st[u] = true ;
    for(int i = h[u] ; i!= -1 ; i = ne[i])
    {
        int s = e[i] ;
        if(!st[s])
        {
            int j = dfs(s) ;
            res = max(j , res) ;
            count += j ;
        }
    }
    res = max(res , n - count) ;
    ans = min(ans , res) ;
    return count ;
}

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 << endl ;
    return 0 ;
}