自动搬运

查看原文

来自洛谷，原作者为

	zhouhuanyi 在量子世界中，所有的未来都同样真实。

搬运于2025-08-24 22:44:54，当前版本为作者最后更新于2023-12-04 20:48:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

令 $dp_{x,d}$ 表示 $x$ 子树内现在根结点上挂着的链的长度为 $d$ 的最大收益，那么转移时只要考虑一个点的子节点如何进行合并，注意到只有 $1,3$ 消，$2,2$ 消两种互消的 $\text{case}$，相当于转移相当于 $\text{fix}$ $a-c=d_{1}(|d_{1}|\leqslant 1)$ 且 $b$ $\text{mod}$ $2=d_{2}$，选择 $a$ 个 $1$，$b$ 个 $2$，$c$ 个 $3$，剩下的全取 $0$，求最大和。考虑给选法分配一个重量与额外重量，将其看做一个二元组，那么令选 $0$ 为 $(1,0)$，选 $1$ 为 $(0,0)$，选 $2$ 为 $(1,1)$，选 $3$ 为 $(2,0)$，现在定义 $(a_{0},b_{0})+(a_{1},b_{1})=(a_{0}+a_{1},b_{0}$ $\text{xor}$ $b_{1})$，现在求拼成 $(a,b)$ 的最大和。如果将 $b$ 的限制去除，这是经典模拟费用流问题，反悔只有 $+2,-1$，所有重量在 $\text{mod}$ $2$ 意义下是凸的，直接闵可夫斯基和即可，加入 $b$ 的限制后其实多记一维 $0/1$ 即可。复杂度 $O(n \log n)$。