Initiate

题目:把一个带权值的树断开一条连线使其变为两个树，且这两部分的权值和之差最小。
算法:用向量组做邻接表存储数据，用dfs将树扫描一遍，从最底部开始判断。

#include<iostream>
#include<vector>
using namespace std;
int n,m,cas;
vector<int>vec[100010];
int per[100010],vis[100010];
long long cnt[100010];
long long total,res;
long long dfs(int t)
{
vis[t]=1;
cnt[t]=per[t];
for(int i=0 ;i<vec[t].size();i++)
{
   int a=vec[t][i];
   if(vis[a])continue;
   cnt[a] = dfs(a);
   cnt[t] +=cnt[a];
   long long temp;
   if(total-cnt[a]>=cnt[a])
    temp=total - 2*cnt[a];
   else
    temp=2*cnt[a]-total;
   if( temp < res ) res=temp;
   }
return cnt[t];
}
int main()
{
int i,j,p,q;
while (scanf("%d%d", &n, &m),n || m)
{
   total=0;
   res=1000000000000000LL;
   for(i=1;i<=n;i++)
   {
    scanf("%d", &per[i]);
    total +=per[i];
    vec[i].clear();
    cnt[i]=0;
    vis[i]=0;
   }
   for(i=1;i<=m;i++)
   {
    scanf("%d%d",&p,&q);
    vec[p].push_back(q);
    vec[q].push_back(p);
   }
   dfs(1);
   printf("Case %d: %lld\n", ++cas, res);
   }
return 0;
}