#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define reg register inline int read() { int res = 0;char ch=getchar();bool fu=0; while(!isdigit(ch))fu|=(ch==‘-‘),ch=getchar(); while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar(); return fu?-res:res; } #define N 2505 int K, n; int P[N], S[N]; struct edge { int nxt, to; }ed[N]; int head[N], cnt; inline void add(int x, int y) { ed[++cnt] = (edge){head[x], y}; head[x] = cnt; } double f[N][N], val[N]; int siz[N], dfn[N], tot; void dfs(int x) { siz[x] = 1; for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; dfs(to); siz[x] += siz[to]; } dfn[x] = ++tot; } void dp(int x) { siz[x] = 1; for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; dp(to); for (reg int j = siz[x] ; j >= 1 ; j --) for (reg int p = 0 ; p <= siz[to] ; p ++) f[x][j + p] = max(f[x][j + p], f[to][p] + f[x][j]); siz[x] += siz[to]; } } int main() { K = read() + 1, n = read(); for (reg int i = 1 ; i <= n ; i ++) S[i] = read(), P[i] = read(), add(read(), i); dfs(0); double l = 0, r = 1e4, mid(0); while(r - l >= 1e-5) { mid = (l + r) / 2; for (reg int i = 1 ; i <= n ; i ++) val[i] = 1.0 * P[i] - 1.0 * S[i] * mid; for (reg int i = 0 ; i <= n ; i ++) for (reg int j = 0 ; j <= K ; j ++) f[i][j] = -1e9; for (reg int i = 0 ; i <= n ; i ++) f[i][0] = 0; for (reg int i = 0 ; i <= n ; i ++) f[i][1] = val[i]; dp(0); if (f[0][K] >= 1e-5) l = mid; else r = mid; } printf("%.3lf\n", l); return 0; }
对于这种有依赖的树形背包，有一种比较常见的优化方法，这种方法只是针对这种选择一个点必须选择其父亲的树上背包问题。
借鉴自一个巨佬的博客。
我们求出这棵树的后序遍历，对于一个点的dfs序是$i$，那么它的子树一定是$[i - siz[x], i]$的一段连续区间，枚举这个点选不选，选的话从$f[i-1]$转移过来，不选的话从$f[i-siz[i]]$转移过来，复杂度$O(NM)$
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define reg register inline int read() { int res = 0;char ch=getchar();bool fu=0; while(!isdigit(ch))fu|=(ch==‘-‘),ch=getchar(); while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar(); return fu?-res:res; } #define N 2505 int K, n; int P[N], S[N]; struct edge { int nxt, to; }ed[N]; int head[N], cnt; inline void add(int x, int y) { ed[++cnt] = (edge){head[x], y}; head[x] = cnt; } double f[N][N], val[N]; int siz[N], dfn[N], tot; void dfs(int x) { siz[x] = 1; for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; dfs(to); siz[x] += siz[to]; } dfn[x] = ++tot; } void dp(int x) { siz[x] = 1; for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; dp(to); siz[x] += siz[to]; } for (reg int j = 1 ; j <= K ; j ++) f[dfn[x]][j] = max(f[dfn[x] - siz[x]][j], f[dfn[x] - 1][j - 1] + val[x]); } int main() { K = read() + 1, n = read(); for (reg int i = 1 ; i <= n ; i ++) S[i] = read(), P[i] = read(), add(read(), i); dfs(0); double l = 0, r = 1e7, mid(0); while(r - l >= 1e-6) { mid = (l + r) / 2; for (reg int i = 0 ; i <= n ; i ++) { f[i][0] = 0; for (reg int j = 1 ; j <= K ; j ++) f[i][j] = -1e9; } for (reg int i = 1 ; i <= n ; i ++) val[i] = 1.0 * P[i] - 1.0 * S[i] * mid; dp(0); if (f[tot][K] >= 1e-6) l = mid; else r = mid; } printf("%.3lf\n", l); return 0; }
原文：https://www.cnblogs.com/BriMon/p/9832595.html
