Brief description:

。。。热身题。。

Analysis:

…

const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 50000 + 5, M = N * 2;

int to[M], nxt[M]; // edge ..
int sz[N], blc[N], hd[N]; // vertx ..
int n, c;


#define v (to[i])
void dfs(int u = 1, int p = 0){

    for(int i=hd[u];i;i=nxt[i]) if (v != p){
        dfs(v, u), sz[u] += sz[v];
        checkMax(blc[u], sz[v]);
    }
    
    checkMax(blc[u], n - sz[u]);
    checkMin(c, blc[u]);
}


int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //ios::sync_with_stdio(false);
    
    RD(n); 

    for (int i=2;i<n<<1;i+=2){
        RD(to[i|1], to[i]);
        nxt[i] = hd[to[i|1]], hd[to[i|1]] = i;
        nxt[i|1] = hd[to[i]], hd[to[i]] = i|1;
    }
        
    fill(sz+1, sz+n+1, 1);
    c = INF, dfs();
    
    REP_1(i, n) if (blc[i] == c) 
        printf("%d ", i);
    
}

External link:

http://poj.org/problem?id=3107

Posted by xiaodao
Category: POJ