poj1655Balancing Act 树的重心,树形dp

第一次dfs求出每个子树的节点数

第二次dfs求答案

这一题是poj1741的基础

[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

int N;
vector<int>son[20010];   //图的存储结构

int vis[20010];    //标记是否访问过
int num[20010];    //子树节点的数量
int dp[20010];    //答案

void dfs_num(int n){
    int len=son[n].size();
    num[n]=1;
    vis[n]=1;
    for(int i=0;i<len;i++){
        int k=son[n][i];            //儿子
        if(vis[k]) continue;
        dfs_num(k);
        num[n]+=num[k];
    }
// printf("@    %d %d\n",n,num[n]);
}

void dfs_node(int n,int from){
    int k,len=son[n].size();
    vis[n]=1;
    dp[n]=0;
    for(int i=0;i<len;i++){
        k=son[n][i];
        if(vis[k]){
            dp[n]=max(dp[n],N-num[n]);
        }
        else{
            dp[n]=max(dp[n],num[k]);
            dfs_node(k,n);
        }
    }
}

int main()
{
    int i,j,k,T,u,v;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        for(i=1;i<=N;i++)    son[i].clear();

        memset(num,0,sizeof(num));
        memset(dp,0,sizeof(dp));

        for(i=1;i<=N-1;i++) {
            scanf("%d%d",&u,&v);
            son[u].push_back(v);
            son[v].push_back(u);
        }
        memset(vis,0,sizeof(vis));      dfs_num(1);
        memset(vis,0,sizeof(vis));      dfs_node(1,-1);
        for(i=j=k=N;i>=1;i--){
            if(k>dp[i]){
                k=dp[i];
                j=i;
            }
            if(k==dp[i]){
                j=i;
            }
        }
        printf("%d %d\n",j,k);
    }
    return 0;
}

/*

2

7
2 6
1 2
1 4
4 5
3 7
3 1

11
1 2
1 3
1 4
2 5
2 6
4 7
4 8
4 9
8 10
8 11

*/

补充：软件开发 , C++ ,