POJ-3140 Contestants Division(樹dp)

題目：http://poj.org/problem?id=3140

題意：給你一棵樹，讓你找一條邊，使得兩顆子樹權值和相差最小，求最小的權值差

思路：直接樹dp，找樹權值和sum和2*子樹權值和的最小內插補點就行了

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
using namespace std;

typedef long long ll;
const int N = +;

struct edge
{
    int to,nxt;
    edge(int t = ,int n = ):to(t),nxt(n){}
}E[N*];
int n,m,a[N],tot,head[N*];
ll dp[N],minn,sum;
void add_edge(int u,int v)
{
    E[tot] = edge(v,head[u]);
    head[u] = tot++;
}
void dfs(int u,int fa)
{
    dp[u] = a[u];
    for(int i = head[u];~i;i = E[i].nxt)
    {
        int v = E[i].to;
        if(v == fa)
            continue;
        dfs(v,u);
        dp[u] += dp[v];
    }
    minn = min(minn,llabs(sum-*dp[u]));
}
int main()
{
    int ca = ;
    while(~scanf("%d%d",&n,&m) && (n || m))
    {
        tot = ;
        memset(head,-,sizeof(head));
        sum = ;
        for(int i = ;i <= n;i++)
            scanf("%d",&a[i]),sum += a[i];
        int u,v;
        while(m--)
        {
            scanf("%d%d",&u,&v);
            add_edge(u,v);
            add_edge(v,u);
        }
        minn = ;
        memset(dp,,sizeof(dp));
        dfs(,-);
        printf("Case %d: %lld\n",++ca,minn);
    }
    return ;
}