题意：一棵树每个结点上都有值，现删掉一条边，使得到的两棵树上的数值和差值最小。
思路：这个题我直接dfs做的，不知道树状dp是什么思路。。一开始看到数据规模有些后怕，后来想到long long 可以达到10^18，我突然就释然了。
整体思路就是，先记录下整棵树的数值之和tot，然后对这棵树进行一遍dfs，每个结点都维护一个num值，num[x]表示结点x和它子树上的数值和。每求出一个结点的num值，就计算下tot - num[x]和num[x]的差值。dfs结束后最小的差值即为结果。
另外，要注意的一点是，如果用res来存储最后结果，初始化应为无穷大，而因为它是long long类型，可以初始化为0x3f3f3f3f3f3f3f3f。如果你还是按照int的大小来初始化为无穷大，会发现wa，就是这么回事。。。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define maxn 100005 5 #define maxp 1000005 6 #define inf 0x3f3f3f3f3f3f3f3f 7 using namespace std; 8 9 struct node 10 { 11 int v, next; 12 }edge[maxp]; 13 int num_edge, head[maxn]; 14 void init_edge() 15 { 16 num_edge = 0; 17 memset(head, -1, sizeof(head)); 18 } 19 void addedge(int a,int b) 20 { 21 edge[num_edge].v = b; 22 edge[num_edge].next = head[a]; 23 head[a] = num_edge++; 24 } 25 26 long long dif(long long a,long long b) 27 { 28 return (a > b) ? a - b : b - a; 29 } 30 31 int stu[maxn], n, m; 32 bool vis[maxn]; 33 long long num[maxn], tot, res; 34 void dfs(int x) 35 { 36 num[x] = stu[x]; 37 vis[x] = 1; 38 for (int i = head[x]; i != -1; i = edge[i].next) 39 { 40 int v = edge[i].v; 41 if (vis[v]) continue; 42 dfs(v); 43 num[x] += num[v]; 44 } 45 res = min(res, dif(num[x], tot - num[x])); 46 } 47 int main() 48 { 49 int cas = 1; 50 while (~scanf("%d%d", &n, &m) && n && m) 51 { 52 tot = 0; 53 for (int i = 1; i <= n; i++) 54 { 55 scanf("%d",&stu[i]); 56 tot += stu[i]; 57 } 58 init_edge(); 59 memset(vis, 0, sizeof(vis)); 60 for (int i = 1; i <= m; i++) 61 { 62 int a, b; 63 scanf("%d%d", &a, &b); 64 addedge(a, b); 65 addedge(b, a); 66 } 67 res = inf; 68 dfs(1); 69 printf("Case %d: %lld ", cas++, res); 70 } 71 return 0; 72 }