poj1655(Balancing Act + 樹形dfs)

    題意：有一顆N個節點的樹，每個節點的Balancing是刪除該節點後所有子樹中節點數目最大的子樹節點數目。問Balancing的最小值與該節點的編號。如果Balancing相同，輸出節點編號較小的。

代碼：

[cpp]
#include<stdio.h> 
#include<string.h> 
#define MAXN 20005 
struct Edge{ 
    int v; 
    int next; 
}edge[MAXN*2]; 
int sum[MAXN*2],son[MAXN]; 
/*
sum[]記載除去"父節點的子樹"的節點數量總和
son[]記錄除去"父節點的子樹"的所有子樹中最大節點數
父節點在該題理解為DFS過程中的上一層節點
*/ 
int head[MAXN],visited[MAXN]; 
int tot; 
int Max(int a,int b) 
{ 
    return a>b ? a : b; 
} 
void addedge(int x,int y) 
{ 
   tot++; 
   edge[tot].v = y; 
   edge[tot].next = head[x]; 
   head[x] = tot; 
     
   tot++; 
   edge[tot].v = x; 
   edge[tot].next = head[y]; 
   head[y] = tot; 
   
} 
void dfs(int x) 
{ 
   visited[x] = 1; 
   int t; 
   for(t=head[x];t!=-1;t=edge[t].next) 
   { 
       if(!visited[edge[t].v]) 
       { 
           dfs(edge[t].v); 
           sum[x] += sum[edge[t].v]; 
           if(son[x] < sum[edge[t].v]) 
               son[x] = sum[edge[t].v]; 
       } 
   } 
} 
int main() 
{ 
     
    int ncase; 
    scanf("%d",&ncase); 
    while(ncase--) 
    { 
        int i,N; 
        int x,y; 
        int id,ans; 
        scanf("%d",&N); 
        tot = 0; 
        memset(head,-1,sizeof(head)); 
        memset(edge,0,sizeof(edge)); 
        for(i=1;i<N;i++) 
        { 
            scanf("%d%d",&x,&y); 
            addedge(x,y); 
        } 
        memset(visited,0,sizeof(visited)); 
        memset(son,0,sizeof(son)); 
        for(i=0;i<=N;i++) 
            sum[i] = 1; 
        dfs(1); 
        id = 1; 
        ans = son[1]; www.2cto.com
        for(i=2;i<N;i++) 
            if(ans > Max(son[i],sum[1]-sum[i]))//sum[1]為整棵樹的節點數量，sum[1]-sum[i]就是父節點子樹的節點數目 
            { 
                ans = Max(son[i],sum[1]-sum[i]); 
                id = i; 
            } 
        printf("%d %d\n",id,ans); 
    } 
    return 0; 
}