poj3140（树的dfs）

题意：给定一棵n棵节点的树，求删去某条边后两个分支的最小差异值。

分析：num[u]表示以u点为根节点的子树的总人数，那么不在该子树的人数和为sum-num[u].dfs遍历一遍即可。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 100010
#define clr(a) (memset(a,0,sizeof(a)))
using namespace std;
struct edge
{
    int next,v;
    edge(){}
    edge(int v,int next):v(v),next(next){}
}e[N*2];
int head[N],tot,n,m;
LL ans,sum,num[N];
LL Abs(LL a)
{
    return a>0?a:-a;
}
void addedge(int u,int v)
{
    e[tot]=edge(v,head[u]);
    head[u]=tot++;
}
void dfs(int u,int fa)
{
    for(int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa)continue;
        dfs(v,u);
        num[u]+=num[v];
    }
    ans=min(ans,Abs(sum-2*num[u]));
}
int main()
{
    int u,v,cas=1;
    while(scanf("%d%d",&n,&m)>0)
    {
        if(n==0&&m==0)break;
        tot=0;
        memset(head,-1,sizeof(head));
        sum=0;
        for(int i=1;i<=n;i++)
            scanf("%lld",&num[i]),sum+=num[i];
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
       ans=1LL<<50;
       dfs(1,-1);
       printf("Case %d: %lld
",cas++,ans);
    }
}

View Code