POJ 1655-Balancing Act（树形dp）

题意：

求n个节点的树中哪个节点删除以后得到的最大连通分量最小。

分析：同上题

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define N 20010

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

int dp[N],n,num[N],used[N];

vector<int>e[N];

int dfs(int root){

    num[root]=;

    used[root]=;

    for(int i=;i<e[root].size();++i){

        int son=e[root][i];

        if(used[son])continue;

        num[root]+=dfs(son);

        dp[root]=max(dp[root],num[son]);

    }

    dp[root]=max(dp[root],n-num[root]);

    return num[root];

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        memset(dp,,sizeof(dp));

        memset(used,,sizeof(used));

        for(int i=;i<=n;++i)

            e[i].clear();

        int a,b;

        for(int i=;i<n-;++i){

            scanf("%d%d",&a,&b);

            e[a].push_back(b);

            e[b].push_back(a);

        }

        dfs();

        int tmp=;

        for(int i=;i<n;++i)

            if(dp[tmp]>dp[i])

                tmp=i;

        printf("%d %d\n",tmp,dp[tmp]);

    }

return ;

}