考察:树形dp(?)
思路:
f[i]表示i往下(包括i)的点权值和.对比学生总和sum-f[i]与f[i]的大小即可.
这题貌似和m没多大关系.m一定=n-1.
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 typedef long long ll; 6 const int N = 100010,M = 1000010; 7 ll f[N],ans,sum; 8 int s[N],h[N],idx,n,m,kcase; 9 struct Road{ 10 int to,ne; 11 }road[M]; 12 void inits() 13 { 14 idx = 0; memset(h,-1,sizeof h); sum = 0; 15 memset(f,0,sizeof f); 16 } 17 void add(int a,int b) 18 { 19 road[idx].to = b; road[idx].ne = h[a],h[a] = idx++; 20 } 21 ll abss(ll a) 22 { 23 if(a<0) return -a; 24 else return a; 25 } 26 ll dfs(int u,int fa) 27 { 28 f[u] = s[u]; 29 for(int i=h[u];i!=-1;i=road[i].ne) 30 { 31 int v = road[i].to; 32 if(v==fa) continue; 33 f[u] += dfs(v,u); 34 } 35 ans = min(ans,abss(sum-f[u]-f[u])); 36 return f[u]; 37 } 38 int main() 39 { 40 while(scanf("%d%d",&n,&m)!=EOF&&(n+m)) 41 { 42 inits(); 43 for(int i=1;i<=n;i++) scanf("%d",&s[i]),sum=sum+s[i]; 44 ans = sum; 45 for(int i=1;i<=m;i++) 46 { 47 int x,y; scanf("%d%d",&x,&y); 48 add(x,y); add(y,x); 49 } 50 dfs(1,-1); 51 printf("Case %d: %lld\n",++kcase,ans); 52 } 53 return 0; 54 }
说实话这题写的我好没把握啊233,抱着感觉会T的想法交了.