poj 3140 Contestants Division 樹的遍歷

poj 3140 Contestants Division 樹的遍歷

題意：

給一棵樹，每個節點有一個值v,現在要去掉一條邊，使分成的兩棵樹的v的和的差值最小。

分析：

水題，注意數據范圍。

代碼：

//poj 3140
//sep9
#include 
using namespace std;
const int maxN=200024;
int n,m,e;
__int64 sum,ans;
struct Edge
{
	int v,next;
}edge[maxN]; 
__int64 v[maxN];
int head[maxN];

__int64 dfs(int p,int u)
{
	__int64 tmp=v[u];	
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].v;
		if(v!=p){
			__int64 t=dfs(u,v);
			ans=min(ans,max(t,sum-t)-min(t,sum-t));
			tmp+=t;
		}
	}
	return tmp;
}

int main()
{
	int cases=0;
	while(scanf("%d%d",&n,&m)==2&&n){
		e=0,sum=0;
		memset(head,-1,sizeof(head));
		for(int i=1;i<=n;++i){
			scanf("%I64d",&v[i]);
			sum+=v[i];
		}
		while(m--){
			int a,b;
			scanf("%d%d",&a,&b);
			edge[e].v=b;edge[e].next=head[a];head[a]=e++;
			edge[e].v=a;edge[e].next=head[b];head[b]=e++;
		}
		ans=sum;
		dfs(-1,1);
		printf("Case %d: %I64d\n",++cases,ans);			
	}
		
	return 0;	
}