POJ-1655 Balancing Act （树形dp,树的重心）

传送门

思路：树形dp，f[u]保存以u为根节点的子树的节点数，那么只要比较答案和f[v]+1和n-f[u]-1的关系就可以了。

dfs一遍，重点在f[u]+=dfs1(v)+w;更新f[u]，bl=max(bl,f[v]+1);和bl=max(bl,n–f[u]–1);更新bl。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
struct node{
int v,w;
};
vector <node>adj[20010];
int n,ans,bans;
int f[20010];
bool vis[20010];
int dfs1(int u)
{
    vis[u]=true;
    f[u]=0;
    int bl=0;
    for(int i=0; i<adj[u].size(); ++i)
    {
        int v = adj[u][i].v;
        int w = adj[u][i].w;
        if(vis[v])
            continue;
        f[u]+=dfs1(v)+w;
        bl=max(bl,f[v]+1);
    }
    bl=max(bl,n-f[u]-1);
    if (bl<bans)
    {
        bans=bl;
        ans=u;
    }
    return f[u];
}
int main()
{
    int w;
    scanf("%d",&w);
    while (w--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; ++i)
            adj[i].clear();
        for(int u=2; u<=n; ++u)
        {
            int v, w;
            scanf("%d%d", &v, &w);
            adj[v].push_back((node){w, 1});
            adj[w].push_back((node){v, 1});
        }
        memset(f,0,sizeof(f));
        memset(vis,false,sizeof(vis));
        ans=bans=0x3f3f3f3f;
        dfs1(1);
        printf("%d %d\n",ans,bans);
    }
    return 0;
}