【题意】：给出一棵树，每个节点都有一个权值。问删除一条边之后，分开的两颗子树的权值之差的最少为多少。
【题解】：dfs一次，把无向树变成有向树。
顺便统计以每个节点为根的子树的权值之和，记为dp[]
然后我们可以枚举每一条边，由于dfs本身就会把所有边都走一次，所以这个枚举的过程可以直接放在dfs里面。
那么对于每个非叶子结点u，设v为u的儿子结点。
ans = min(ans, abs(sum - 2 * dp[v])), 其中 sum = ∑val[i].
本题注意要用long long.
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 using namespace std;
9 #define pb push_back
10 #define ll long long
11 #define maxn 100050
12 vector<int> vec[maxn];
13 const ll inf = 100000000000000LL;
14 int n, m;
15 ll val[maxn], dp[maxn], sum, ans;
16
17 ll ABS(ll x) {
18 return (x > 0) ? x : (-x);
19 }
20
21 void dfs(int u, int fa) {
22 int size = vec[u].size();
23 dp[u] = val[u];
24 for(int i = 0; i < size; i++) {
25 int v = vec[u][i];
26 if(v == fa) continue;
27 dfs(v, u);
28 dp[u] += dp[v];
29 ans = min(ABS(sum - 2 * dp[v]), ans);
30 }
31 }
32
33 int main() {
34 int Case = 1, u, v;
35 while(~scanf("%d%d", &n, &m)) {
36 if(!n && !m) break;
37 for(int i = 0; i < maxn; i++) vec[i].clear();
38 ans = inf, sum = 0;
39 for(int i = 1; i <= n; i++) {
40 scanf("%lld", &val[i]);
41 sum += val[i];
42 }
43 for(int i = 0; i < m; i++) {
44 scanf("%d%d", &u, &v);
45 vec[u].pb(v), vec[v].pb(u);
46 }
47 dfs(1, -1);
48 printf("Case %d: %lld\n", Case++, ans);
49 }
50 return 0;
51 }
52