【題意】：給出一棵樹(shù)，每個(gè)節(jié)點(diǎn)都有一個(gè)權(quán)值。問(wèn)刪除一條邊之后，分開(kāi)的兩顆子樹(shù)的權(quán)值之差的最少為多少。

【題解】：dfs一次，把無(wú)向樹(shù)變成有向樹(shù)。
               順便統(tǒng)計(jì)以每個(gè)節(jié)點(diǎn)為根的子樹(shù)的權(quán)值之和，記為dp[]
               然后我們可以枚舉每一條邊，由于dfs本身就會(huì)把所有邊都走一次，所以這個(gè)枚舉的過(guò)程可以直接放在dfs里面。
               那么對(duì)于每個(gè)非葉子結(jié)點(diǎn)u，設(shè)v為u的兒子結(jié)點(diǎn)。
                        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