【題意】：shadow酷愛探險，這次shadow來到了一個洞穴中，他發現這個幽深的洞穴由一些房間（相對較為寬敞的區域）和連接這些房間的通道構成，它們形成了一個樹形結構。當shadow探索完整個洞穴出來后，他覺得這里可以作為一個旅游景點來開發，但首先他必須解決這個洞穴中的照明問題。由于這個洞穴中的通道都較為筆直，因而在洞穴中的任意房間建立照明設施都可以照亮與其直接相連的所有房間，但在每個房間建立照明設施所需的費用又因地形不同而不同，所以shadow想知道要照亮整個洞穴所需的最少費用是多少。
【題解】：與poj 3659類似，只是每個點有一個權值而已。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 50050
22 #define maxm 500500
23 const ll inf = 1LL << 60;
24 ll val[maxn], dp[maxn][3];
25 int n;
26 int eh[maxn], tot;
27 struct Edge {
28 int v, next;
29 }et[maxm];
30
31 void init() {
32 tot = 0;
33 memset(eh, -1, sizeof(eh));
34 }
35
36 void addedge(int u, int v) {
37 Edge e = {v, eh[u]};
38 et[tot] = e;
39 eh[u] = tot++;
40 }
41
42 void dfs(int u, int fa) {
43 dp[u][0] = val[u];
44 dp[u][1] = inf;
45 dp[u][2] = 0;
46 bool isleaf = true;
47 for(int i = eh[u]; i != -1; i = et[i].next) {
48 int v = et[i].v;
49 if(v == fa) continue;
50 dfs(v, u);
51 isleaf = false;
52 dp[u][0] += min(dp[v][0], dp[v][2]);
53 dp[u][2] += min(dp[v][0], dp[v][1]);
54 }
55 if(!isleaf) {
56 for(int i = eh[u]; i != -1; i = et[i].next) {
57 int v = et[i].v;
58 if(v == fa) continue;
59 dp[u][1] = min(dp[u][1], dp[u][2] - min(dp[v][0], dp[v][1]) + dp[v][0]);
60 }
61 }
62 }
63
64 int main() {
65 int T, u, v, Case = 1;
66 scanf("%d", &T);
67 while(T--) {
68 scanf("%d", &n);
69 init();
70 for(int i = 1; i <= n; i++) {
71 scanf("%I64d", &val[i]);
72 }
73 for(int i = 1; i < n; i++) {
74 scanf("%d%d", &u, &v);
75 addedge(u, v), addedge(v, u);
76 }
77 dfs(1, -1);
78 printf("Case %d: %I64d\n", Case++, min(dp[1][0], dp[1][1]));
79 }
80 return 0;
81 }
82