本文共 2032 字，大约阅读时间需要 6 分钟。
本文出自
/**===================================================== * This is a solution for ACM/ICPC problem * * @source : zoj-3626 Treasure Hunt I * @description : 树形dp * @author : shuangde * @blog : blog.csdn.net/shuangde800 * @email : zengshuangde@gmail.com * Copyright (C) 2013/08/26 16:23 All rights reserved. *======================================================*/#include #include #include #include #include #include #include #include #include #include #define MP make_pair using namespace std; typedef pair PII; typedef long long int64; const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; const int MAXN = 110; int n, k, m; vector adj[MAXN]; int val[MAXN]; bool vis[MAXN]; int f[MAXN][2*MAXN]; void dfs(int u) { vis[u] = true; for (int i = 0; i <= m; ++i) f[u][i] = val[u]; for (int e = 0; e < adj[u].size(); ++e) { int v = adj[u][e].first; int w = adj[u][e].second; if (vis[v]) continue; dfs(v); for (int i = m; i >= 0; --i) { for (int j = 2*w; j <= i; ++j) { f[u][i] = max(f[u][i], f[u][i-j] + f[v][j-2*w]); } } } } int main(){ while (~scanf("%d", &n)) { // init for (int i = 0; i <= n; ++i) adj[i].clear(); for (int i = 1; i <= n; ++i) scanf("%d", &val[i]); for (int i = 0; i < n - 1; ++i) { int u, v, w; scanf("%d %d %d", &u, &v, &w); adj[u].push_back(MP(v, w)); adj[v].push_back(MP(u, w)); } scanf("%d %d", &k, &m); memset(f, 0, sizeof(f)); memset(vis, 0, sizeof(vis)); dfs(k); printf("%d\n", f[k][m]); } return 0; }