[PA2021] Poborcy podatkowi

zhouhuanyi · 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)。