2025年9月训练记录
2025/9/26
abc416_f
题意：树上选\(k\)条不相交的链，使得其贡献和最大.
可以考虑树形\(dp\).
考虑状态的设计如下：设\(dp_{u,i,0/1/2}\)表示当前选了以\(u\)为根的子树，且当前子树的根节点的状态为\(0/1/2\)的最大子树贡献.
- \(0:\)所选的子树不在任何一条链中
- \(1:\)所选的子树留了向上转移的接口，可以作为一条链向上拼接
- \(2:\)所选的子树不留向上转移的接口，不能作为链向上拼接
可以以树形背包的方式去做转移。
首先根据定义可以得到这样的转移：
- \(dp_{u,i+j,0}\leftarrow max(dp_{u,i,0}+max(dp_{v,j,0},dp_{v,j,1},dp_{v,j,2}))\)
- \(dp_{u,i+j,1}\leftarrow max(dp_{u,i,1}+max(dp_{v,j,0},dp_{v,j,1},dp_{v,j,2}))\)
- \(dp_{u,i+j,2}\leftarrow max(dp_{u,i,2}+max(dp_{v,j,0},dp_{v,j,1},dp_{v,j,2}))\)
考虑拼出一条留接口的链的转移：
- \(dp_{u,i+j,1}\leftarrow max(dp_{u,i,0}+dp_{v,j,1}+a_u)\)
同理，考虑不留接口的向上转移，值得注意的是，你把\(u\)节点同时接入两条边，会让链数减\(1\)，故转移方程如下：
- \(dp_{u,i+j-1,2}\leftarrow max(dp_{u,i,1}+dp_{v,j,1})\)
注意保证\(dp\)的无后效性，可以用滚动数组处理一下.
时间复杂度\(O(nk^2)\).