题目链接： https://hihocoder.com/contest/offers52/problem/3
解题思路： 树形DP。对于每个节点，计算该节点出席和不出席两种情况需要的酒量。有：
dp[i][0] = sum(max(dp[j][0], dp[j][1])) j 是 i 的孩子
dp[i][1] = a[i] + sum(max(dp[j][0], dp[j][1] - a[j] / 2.0)) j 是 i 的孩子节点。 （后一个式子dp[j][1]是以j为根的子树在j出席的情况下的最大酒量，那么在j的父亲节点i出席的情况下，j只能喝a[j]/2，所以最终是dp[j][1] - a[j]/ 2.0）
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int imax_n = 100005; 5 int head[imax_n]; 6 7 struct Edge{ 8 int u, v; 9 Edge(int u, int v):u(u),v(v) 10 { 11 } 12 Edge(){} 13 } e[imax_n]; 14 int next_edge[imax_n]; 15 int cnt = 0; 16 17 int a[imax_n]; 18 int n; 19 20 double dp[imax_n][2]; 21 22 int dfs(int u) 23 { 24 if (u == -1) 25 { 26 return 0; 27 } 28 dp[u][0] = 0; 29 dp[u][1] = a[u-1]; 30 for (int i = head[u]; i != -1; i = next_edge[i]) 31 { 32 int v = e[i].v; 33 dfs(v); 34 dp[u][0] += max(dp[v][0], dp[v][1]); 35 dp[u][1] += max(dp[v][0], dp[v][1] - a[v-1] / 2.0); 36 } 37 return 1; 38 } 39 40 int main() 41 { 42 scanf("%d", &n); 43 for (int i = 0; i < n; ++i) 44 { 45 scanf("%d", &a[i]); 46 } 47 memset(head, -1, sizeof(head)); 48 memset(next_edge, -1, sizeof(next_edge)); 49 int u, v; 50 int father = -1; 51 for (int i = 1; i < n; ++i) 52 { 53 scanf("%d%d",&u,&v); 54 if (father == -1 || father == v) 55 { 56 father = u; 57 } 58 e[cnt].u = u; 59 e[cnt].v = v; 60 next_edge[cnt] = head[u]; 61 head[u] = cnt++; 62 } 63 dfs(father); 64 double ans = max(dp[father][0], dp[father][1]); 65 printf("%.1f ", ans); 66 return 0; 67 }