题目链接： HDU 4616 Game 题意： 给一个 n 个节点和n−1条边的树。每个节点代表一个房间，每个房间都放有一个价值为正的礼物，有的房间有陷阱，有的房间没陷阱，最多可以经过 C 个陷阱（第C个陷阱时就应该停止），可以从任意的房间开始行走，每个房间只能走一次，求获得的礼物的最大价值和？ 数据范围： n≤5∗104,1≤C≤3 分析： 用 dp[u][i] 表示从 u 出发经过i个陷阱可以获得的最大价值，第一次 dfs 记录从 u 的子树得到的结果，第二遍dfs得到从父亲方向的到的结果，所以需要对每种 dp[u][i] 记录最大和次大，以及取得最大时的 id[u] 。 两遍 dfs ，注意下细节就好了。 时间复杂度： O(n∗C)
#include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; typedef long long ll; const int MAX_N = 50010; int T, n, total, C; ll value[MAX_N], dp[MAX_N][5][5]; int head[MAX_N], trap[MAX_N], id[MAX_N][5]; struct Edge { int v, next; } edge[MAX_N * 2]; void AddEdge (int u, int v) { edge[total].v = v; edge[total].next = head[u]; head[u] = total++; } void dfs_son(int u, int p) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v, t = trap[u]; if (v == p) continue; dfs_son(v, u); for (int j = 1; j <= C - t; ++j) { ll son = dp[v][j][0] + value[u]; if (son > dp[u][j + t][0]) { dp[u][j + t][1] = dp[u][j + t][0]; dp[u][j + t][0] = son; id[u][j + t] = v; } else if (son > dp[u][j + t][1]) { dp[u][j + t][1] = son; } } } } void dfs_father(int u, int p) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v, t = trap[edge[i].v]; if (v == p) continue; for (int j = 1; j <= C - t; ++j) { ll father; if (id[u][j] == v) father = dp[u][j][1] + value[v]; else father = dp[u][j][0] + value[v]; if (father > dp[v][j + t][0]) { dp[v][j + t][1] = dp[v][j + t][0]; dp[v][j + t][0] = father; id[v][j + t] = u; } else if (father > dp[v][j + t][1]) { dp[v][j + t][1] = father; } } dfs_father(v, u); } } int main() { scanf("%d", &T); while (T--) { scanf("%d%d", &n, &C); memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; ++i) { scanf("%lld%d", &value[i], &trap[i]); for (int j = 1; j <= C; ++j) { dp[i][j][0] = value[i]; id[i][j] = i; } } memset(head, -1, sizeof(head)); total = 0; for (int i = 1; i < n; ++i) { int u, v; scanf("%d%d", &u, &v); AddEdge(u, v); AddEdge(v, u); } dfs_son(0, -1); dfs_father(0, -1); ll ans = 0; for (int i = 0; i < n; ++i) { ans = max(ans, dp[i][C][0]); } printf("%lld\n", ans); } return 0; }