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

TODO

挖坑待填

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

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

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

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

那么 fnow,tot,j=max(fnow,tot,j,fnow,tot−1,j−k+fv,mxtot,k) <0A> <0A> <0A> <0A> , <0A> <0A> <0A> , <0A>

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

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

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪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])) { <0A> <0A> [ <0A> ] [ <0A> + <0A> ] [ 0 ] [ 0 ]

∑ <0A> <0A> [ <0A> ] [ <0A> ] [ 0 ] [ 0 ] × <0A> <0A> [ <0A> ] [ <0A> ] [ 0 ] [ 1 ] <0A> <0A> [ <0A> ] [ <0A> + <0A> ] [ 1 ] [ 0 ]

∑ <0A> <0A> [ <0A> ] [ <0A> ] [ 1 ] [ 0 ] × ( <0A> <0A> [ <0A> ] [ <0A> ] [ 0 ] [ 0 ] + <0A> <0A> [ <0A> ] [ <0A> ] [ 0 ] [ 1 ] ) <0A> <0A> [ <0A> ] [ <0A> + <0A> ] [ 0 ] [ 1 ]

∑ ( <0A> <0A> [ <0A> ] [ <0A> ] [ 0 ] [ 1 ] × ( <0A> <0A> [ <0A> ] [ <0A> ] [ 0 ] [ 1 ] + <0A> <0A> [ <0A> ] [ <0A> ] [ 1 ] [ 1 ] ) + <0A> <0A> [ <0A> ] [ <0A> ] [ 0 ] [ 0 ] × <0A> <0A> [ <0A> ] [ <0A> ] [ 1 ] [ 1 ] ) <0A> <0A> [ <0A> ] [ <0A> + <0A> ] [ 1 ] [ 1 ]

∑ ( <0A> <0A> [ <0A> ] [ <0A> ] [ 1 ] [ 0 ] × ( <0A> <0A> [ <0A> ] [ <0A> ] [ 1 ] [ 0 ] + <0A> <0A> [ <0A> ] [ <0A> ] [ 1 ] [ 1 ] ) + <0A> <0A> [ <0A> ] [ <0A> ] [ 1 ] [ 1 ] × ( <0A> <0A> [ <0A> ] [ <0A> ] [ 0 ] [ 0 ] + <0A> <0A> [ <0A> ] [ <0A> ] [ 0 ] [ 1 ] + <0A> <0A> [ <0A> ] [ <0A> ] [ 1 ] [ 0 ] + <0A> <0A> [ <0A> ] [ <0A> ] [ 1 ] [ 1 ] ) )

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

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

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

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

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