[PA2021] Poborcy podatkowi-526互联

令 \(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)\)。