这叫树形DP吗。。？断开某条边 求剩下两颗树数权值和的差最小
dfs一遍 枚举边 查了n久 wa n次 dp数组没初始化。。
在poj上1A感觉应该挺爽
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define N 100010
#define M 1000010
#define LL long long
LL dp[M<<],p[N];
struct node
{
int u,v,next;
}ed[M<<];
int head[N],t,n,m;
void init()
{
t = ;
memset(head,-,sizeof(head));
}
void add(int u,int v)
{
ed[t].u = u;
ed[t].v = v;
ed[t].next = head[u];
head[u] = t++;
}
LL dfs(int pre,int u,int e)
{
int i;
LL sum=p[u];
for(i = head[u] ; i != - ; i = ed[i].next)
{
int v = ed[i].v;
if(v==pre)
continue;
sum+=dfs(u,v,i);
}
dp[e] = sum;
return dp[e];
}
int main()
{
int i,kk=;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==)
break;
init();kk++;
memset(dp,,sizeof(dp));
LL s=;
for(i =; i <= n; i++)
{
scanf("%lld",&p[i]);
s+=p[i];
}
for(i = ; i <= m ;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(-,i,);
LL ans = s,o;
for(i = ; i < t ; i++)
{
if(s-dp[i]>dp[i])
o = s-dp[i]-dp[i];
else
o = dp[i]-(s-dp[i]);
if(o<ans)
ans = o;
}
printf("Case %d: ",kk);
printf("%lld\n",ans);
}
return ;
}