IOI '03 Practice Task - Balancing Act ( Easy Tree center )

PEG Judge - IOI '03 Practice Task - Balancing Act
The idea of a tree center, is a node in the tree that would minimize the maximum subtree size after it is removed. Carefully simulating it without recomputing will do alright. O( n ).

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e4 + 2;

int n;
vector<int> G[ MAXN ];

void init(){
    for(int i = 1; i <= n; ++i)
        G[ i ].clear();
}

int ans;
int max_c_size[ MAXN ];
int size[ MAXN ];

int dfs(int u, int fa){
    max_c_size[ u ] = size[ u ] = 1;
    for(int v: G[ u ]){
        if( v == fa ) continue;
        int c_size = dfs( v, u );
        max_c_size[ u ] = max<int>( max_c_size[ u ], c_size );
        size[ u ] += c_size;
    }
    max_c_size[ u ] = max<int>( max_c_size[ u ], n - size[ u ] );
    if( ans == -1 || max_c_size[ u ] < max_c_size[ ans ] ||
                   ( max_c_size[ u ] == max_c_size[ ans ] && u < ans ) )
        ans = u;
    return size[ u ];
}

void solve(){
    ans = -1;
    dfs( 1, -1 );
    printf("%d %d\n", ans, max_c_size[ ans ]);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n - 1; ++i){
        int u, v; scanf("%d%d", &u, &v);
        G[ u ].push_back( v );
        G[ v ].push_back( u );
    }
    solve();
    return 0;
}