本文共 2450 字，大约阅读时间需要 8 分钟。
本文出自
/**===================================================== * This is a solution for ACM/ICPC problem * * @source : uva-1407 Caves * @description : 树形背包dp * @author : shuangde * @blog : blog.csdn.net/shuangde800 * @email : zengshuangde@gmail.com * Copyright (C) 2013/08/23 14:06 All rights reserved. *======================================================*/#include #include #include #include #include #include #include #define MP make_pair using namespace std; typedef pair PII; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 510; vector adj[MAXN]; int n, q; int tot[MAXN]; int f[MAXN][MAXN][2]; bool vis[MAXN]; int dfs(int u) { vis[u] = true; tot[u] = 1; // 统计子树节点个数 for (int i = 0; i < adj[u].size(); ++i) { int v = adj[u][i].first; int w = adj[u][i].second; if (vis[v]) continue; tot[u] += dfs(v); vis[v] = false; } // dp f[u][1][0] = f[u][1][1] = 0; for (int i = 0; i < adj[u].size(); ++i) { int v = adj[u][i].first; int w = adj[u][i].second; if (vis[v]) continue; for (int s = tot[u]; s >= 1; --s) { for (int j = 1; j <= tot[v] && j < s; ++j) { int tmp1 = f[u][s-j][1] + f[v][j][0] + w; int tmp2 = f[u][s-j][0] + f[v][j][1] + 2 * w; f[u][s][0] = min(f[u][s][0], min(tmp1, tmp2)); f[u][s][1] = min(f[u][s][1], f[u][s-j][1] + f[v][j][1] + 2 * w); } } } return tot[u]; } int main(){ int cas = 1; while (~scanf("%d", &n) && n) { // init for (int i = 0; i <= n; ++i) adj[i].clear(); for (int i = 0; i < n - 1; ++i) { int u, v, w; scanf("%d%d%d", &v, &u, &w); adj[u].push_back(MP(v, w)); } memset(vis, 0, sizeof(vis)); memset(f, INF, sizeof(f)); dfs(0); scanf("%d", &q); printf("Case %d:\n", cas++); while (q--) { int d; scanf("%d", &d); for (int i = n; i >= 1; --i) { if (f[0][i][0] <= d) { printf("%d\n", i); break; } } } } return 0; }