爱在西元前 题解

· · 题解

简单换根 dp。预估难度提高。

菊花图部分分

显然原本的最大权独立集只可能是中心结点单点集或者非负（权值为 0 任意）叶子结点集。

若两者权值相同，则只可能改变一个负权叶子结点的权值使之加入独立集，对称差至多为 1，这样的叶子结点不存在则对称差必然为 0；否则只需将一种情况转化为另一种情况即可让点数变化尽可能多。

具体地，若原来的最大权独立集为单点，则可以改变负权叶子结点的权值（若不存在则任意增加一个叶子结点的权值）；若原来的最大权独立集为叶子结点集，则只能改变中心结点的权值。

链部分分

相当于序列上的情形，其本质与树上问题差异不大，不再赘述。想明白序列上的情况或许对树上有一定帮助（？）不过感觉有一些经验的选手基本上可以直接解决树上情形。

树形 dp 解法

首先回顾经典树上最大权独立集状态，f_{u,0/1} 表示 u 的子树内，不选/选 u 的最大权独立集权值。

注意到 u 为根时，若 f_{u,0}>f_{u,1}，则改变 u 的权值至一足够大正整数（可视为 +\infty）时最大权独立集将变为 f_{u,1} 对应的某个独立集。

若原本 f_{u,1}>f_{u,0}，则改变 u 的权值至一足够小负整数（可视为 -\infty）后最大权独立集将变为 f_{u,0} 对应的某个独立集。

否则 f_{u,1}=f_{u,0}，无论如何改变权值，一定存在一个原树的最大权独立集在改变后的树中仍是最大权独立集。

因此我们只需求出当 u 为根且 f_{u,0}\neq f_{u,1} 时，f_{u,0} 与 f_{u,1} 对应独立集的对称差点数最小值即可。

考察状态转移方程：f_{u,0}=\sum_{x\in son_u}\max\{f_{x,0},f_{x,1}\},f_{u,1}=v(u)+\sum_{x\in son_u}f_{x,0}，发现当且仅当 f_{x,1}>f_{x,0} 时，x,0/1 的对称差对 u,0/1 的对称差有贡献。否则我们可以贪心地让 x 的子树内的点状态都不变动，这样变动的点数一定能取到最少可能值。

记 g_u 为在 u 的子树内，u,0/1 对应独立集的对称差最小点数。则由以上分析可得转移方程 g_u=1+\sum_{v\in son_u}g_v[f_{v,1}>f_{v,0}]。

枚举根树形 dp 即可做到 O(n^2)，换根即可做到 O(n)。