python/TangDou/Topic/【树上背包】专题.md

TODO

挖坑待填

https://blog.csdn.net/yingxue_cat/article/details/133648992

树上背包
发现这个也不会。枯。希望现学来得及吧。

P2014 [CTSC1997] 选课
虽然以前写过，但似乎是没咋看懂式子稀里糊涂敲上去的(？
啊啊啊以前好多这种稀里糊涂照着题解思路/老师代码贺上去的题，每当提起我都记得做过，每当考到就发现不会，深受其害/ll

这题是个森林，则对每棵树的根节点向 0
0
 连边，使之变成一棵树。
设 fi,j,k
<EFBFBD>
<EFBFBD>
,
<EFBFBD>
,
<EFBFBD>
 表示子树 i
<EFBFBD>
 的前 j
<EFBFBD>
 个儿子，已经选了 k
<EFBFBD>
 门课的最大值。注意：必须选点 i
<EFBFBD>

那么 fnow,tot,j=max(fnow,tot,j,fnow,tot−1,j−k+fv,mxtot,k)
<EFBFBD>
<EFBFBD>
<EFBFBD>
<EFBFBD>
,
<EFBFBD>
<EFBFBD>
<EFBFBD>
,
<EFBFBD>
=
max
(
<EFBFBD>
<EFBFBD>
<EFBFBD>
<EFBFBD>
,
<EFBFBD>
<EFBFBD>
<EFBFBD>
,
<EFBFBD>
,
<EFBFBD>
<EFBFBD>
<EFBFBD>
<EFBFBD>
,
<EFBFBD>
<EFBFBD>
<EFBFBD>
−
1
,
<EFBFBD>
−
<EFBFBD>
+
<EFBFBD>
<EFBFBD>
,
<EFBFBD>
<EFBFBD>
<EFBFBD>
<EFBFBD>
<EFBFBD>
,
<EFBFBD>
)
。同样注意 k
<EFBFBD>
 只能循环到 j−1
<EFBFBD>
−
1
。
类似背包进行滚动数组优化。(似乎滚动了反而更好写(？)
也不知道自己到底会没会/kk

P4516 [JSOI2018] 潜入行动
题面看起来还挺套路，但我不会，树形 dp 是真忘光了啊啊啊啊啊怎么办
式子好长不想写...算了口胡一下吧。
设 dp[u][j][0/1][0/1]
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
/
1
]
[
0
/
1
]
 表示子树 u
<EFBFBD>
 里放了 j
<EFBFBD>
 个，点 u
<EFBFBD>
 放了/没放，是否已经被监听。
于是滚动数组一下推出长下面这样的转移柿子↓
↓

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪dp[x][i+j][0][0]=∑dp[x][i][0][0]×dp[v][j][0][1]dp[x][i+j][1][0]=∑dp[x][i][1][0]×(dp[v][j][0][0]+dp[v][j][0][1])dp[x][i+j][0][1]=∑(dp[x][i][0][1]×(dp[v][j][0][1]+dp[v][j][1][1])+dp[x][i][0][0]×dp[v][j][1][1])dp[x][i+j][1][1]=∑(dp[x][i][1][0]×(dp[v][j][1][0]+dp[v][j][1][1])+dp[x][i][1][1]×(dp[v][j][0][0]+dp[v][j][0][1]+dp[v][j][1][0]+dp[v][j][1][1]))
{
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
+
<EFBFBD>
]
[
0
]
[
0
]
=
∑
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
]
[
0
]
×
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
]
[
1
]
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
+
<EFBFBD>
]
[
1
]
[
0
]
=
∑
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
1
]
[
0
]
×
(
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
]
[
0
]
+
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
]
[
1
]
)
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
+
<EFBFBD>
]
[
0
]
[
1
]
=
∑
(
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
]
[
1
]
×
(
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
]
[
1
]
+
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
1
]
[
1
]
)
+
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
]
[
0
]
×
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
1
]
[
1
]
)
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
+
<EFBFBD>
]
[
1
]
[
1
]
=
∑
(
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
1
]
[
0
]
×
(
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
1
]
[
0
]
+
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
1
]
[
1
]
)
+
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
1
]
[
1
]
×
(
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
]
[
0
]
+
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
0
]
[
1
]
+
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
1
]
[
0
]
+
<EFBFBD>
<EFBFBD>
[
<EFBFBD>
]
[
<EFBFBD>
]
[
1
]
[
1
]
)
)

卡 long long 空间，要强制类型转换。我不管，我胡了就是我写了！(确信

不知道啥题
OI wiki 为什么给我推黑题啊，不会/kk
所以写到这吧awa

树形 DP
范学长讲树上问题，顺路回来更新一波。

CF822F Madness
贪心题。胡了篇 lg 题解。

P2607 [ZJOI2008] 骑士
基环树上的 dp。第一次做这种题(？
对于每个基环树，dfs 找到环的那条边，对于这条边分别钦定 u
<EFBFBD>
 不选/v
<EFBFBD>
 不选，分别 dp 即可。
转移显然。
实现的时候写麻烦了，直接并查集判环就可以，不用 dfs。