【题意】：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