已知(2+1)?種做法

分別是：

• 按dfs序倒推

Link

BZOJ2427代碼

int sta[N], dfn[N], low[N], w[N], val[N], dp[N][505], n, m, top, W[N], V[N], fa[N], l[N], cnt[N], siz[N], bel[N], idx; vint G[N];bitset<N>ins, vis; void tarjan(int u) {static int tar = 0, idx = 0;ins[sta[++top] = u] = 1, dfn[u] = low[u] = ++idx;for (vint::iterator v = G[u].begin(); v != G[u].end(); ++v) {if (!dfn[*v]) {tarjan(*v);low[u] = min(low[u], low[*v]);}else if (ins[*v]) low[u] = min(low[u], dfn[*v]);}if (dfn[u] == low[u]) {int v; ++tar;do {++cnt[tar];ins[v = sta[top--]] = 0, bel[v] = tar;w[tar] += W[v], val[tar] += V[v];}while (u != v);} } void dfs(int u) {l[++idx] = u, siz[u] = 1;for (vint::iterator v = G[u].begin(); v != G[u].end(); ++v) dfs(*v), siz[u] += siz[*v]; }void init() {}void solve() {in, n, m;lo1(i, n) in, W[i];lo1(i, n) in, V[i];lo1(i, n) G[fa[i] = in].pb(i);lo1(i, n) if (!dfn[i]) tarjan(i); lo0(i, n + 1) G[i].clear();lo1(i, n)if (cnt[bel[i]] > 1 && !vis[bel[i]]) G[0].pb(bel[i]), vis[bel[i]] = 1; else if (cnt[bel[i]] == 1) G[bel[fa[i]]].pb(bel[i]);dfs(0);memset(dp, 0xbf, sizeof dp);dp[idx + 1][0] = 0;dl1(i, idx) {int x = l[i];lo0(j, m + 1) {chmax(dp[i][j], max(dp[i + siz[x]][j], 0));if (w[x] <= j) chmax(dp[i][j], dp[i + 1][j - w[x]] + val[x]);}}int ans = 0;lo1(i, m) chmax(ans, dp[1][i]);out, ans; }int main() { #ifdef QvvQ// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);Dbg = 1; #endifint T = 1;while (T--) init(), solve(); #ifdef QvvQfprintf(stderr, "\ntime:%.5fms", clock() * 1000.0 / CLOCKS_PER_SEC); #endifreturn 0; }

• 2009集訓隊論文中的寫法

dp(u res)表示選擇了根到u的路徑上的所有點　再在u左側(已經遍歷過的部分)和u的子樹內選擇重量最大為res的物品的最大價值

BZOJ2427代碼

w[N], val[N], dp[N][505], n, m, top, W[N], V[N], fa[N], cnt[N], bel[N]; vint G[N];bitset<N>ins, vis; void tarjan(int u) {static int tar = 0, idx = 0;ins[sta[++top] = u] = 1, dfn[u] = low[u] = ++idx;for (vint::iterator v = G[u].begin(); v != G[u].end(); ++v) {if (!dfn[*v]) {tarjan(*v);low[u] = min(low[u], low[*v]);}else if (ins[*v]) low[u] = min(low[u], dfn[*v]);}if (dfn[u] == low[u]) {int v; ++tar;do {++cnt[tar];ins[v = sta[top--]] = 0, bel[v] = tar;w[tar] += W[v], val[tar] += V[v];}while (u != v);} } void DP(int u, int res) {if (!res) return ;for (vint::iterator it = G[u].begin(); it != G[u].end(); ++it) {copy(dp[u] + 1, dp[u] + 1 + res, dp[*it] + 1);DP(*it, res >= w[*it] ? res - w[*it] : res);dl(j, res, w[*it]) chmax(dp[u][j], dp[*it][j - w[*it]] + val[*it]);} }void init() {}void solve() {in, n, m;lo1(i, n) in, W[i];lo1(i, n) in, V[i];lo1(i, n) G[fa[i] = in].pb(i);lo1(i, n) if (!dfn[i]) tarjan(i); lo0(i, n + 1) G[i].clear();lo1(i, n)if (cnt[bel[i]] > 1 && !vis[bel[i]]) G[0].pb(bel[i]), vis[bel[i]] = 1; else if (cnt[bel[i]] == 1) G[bel[fa[i]]].pb(bel[i]);DP(0, m - w[0]);out, dp[0][m] + val[0]; }int main() { #ifdef QvvQ// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);Dbg = 1; #endifint T = 1;while (T--) init(), solve(); #ifdef QvvQfprintf(stderr, "\ntime:%.5fms", clock() * 1000.0 / CLOCKS_PER_SEC); #endifreturn 0; }

另一種在dfs過程中枚舉 i <- siz[u] to 0和j <- 0 to siz[v]的做法 (好像跟上面兩種不通用，如果通用求指正)

一個這個寫法的題目

轉載于:https://www.cnblogs.com/storz/p/10446892.html

總結

以上是生活随笔為你收集整理的树形背包小结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。