poj3140——树形搜索

题目大意：每个节点有一个权值，可从任一边将树一分为二，求两边权和之差的最小值

附：题目链接

建树过程和上一道题一样，同时求出每个节点管辖子树的规模size，然后在dfs函数中判断：把当前点及其以下从树上割开时，两者之差是否更小，ans初始值设为所有点权和即可。

出现问题：

1.runtime error，vector<int>设为全局变量然后忘记了每次都要加上clear()处理。。

2.wrong answer，受了上一道题影响，，还认为每个点大小为1，sz数组忘记用a数组初始化。

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

vector<int>G[100000+4000];
long long sum;
long long ans;
long long sz[100000+4000],a[100000+4000];
int n,m;

void dfs(int u,int par){
    sz[u]=a[u];
    for(int i=0;i<(int)G[u].size();i++){
        if(G[u][i]!=par)
            dfs(G[u][i],u);
    }
    for(int i=0;i<(int)G[u].size();i++)
        if(G[u][i]!=par)
            sz[u]+=sz[G[u][i]];
    ans=min(ans,sum-2*sz[u]>0?sum-2*sz[u]:2*sz[u]-sum);
}

int main(){
    int k=1;
    while(scanf("%d%d",&n,&m)==2){
        if(m+n==0)
            break;
        sum=0;
        for(int i=1;i<=n;i++){
            scanf("%I64d",&a[i]);
            sum+=a[i];
            G[i].clear();
        }
        ans=sum;
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(1,0);
        printf("Case %d: %I64d\n",k++,ans);
    }
    return 0;
}