题解

思路

静态树形动态规划

先把树以节点 $1$ 为根。令 $f_{u,0}$ 表示在节点 $u$ 的子树内、不选 $u$ 时的最大权独立集权值，$f_{u,1}$ 表示选择 $u$ 时的最大值。对每个儿子 $v$，有

$$f_{u,0}=\sum_v\max(f_{v,0},f_{v,1}),\qquad f_{u,1}=a_u+\sum_v f_{v,0}.$$

空集合法，所以叶子的“不选”状态为 $0$，负权节点也不会迫使答案变成负数。一次完整树形 DP 的复杂度为 $O(n)$，因此可以解决 $n,m\le 1000$ 的子任务。

做法

把重链转移写成矩阵

每个非叶节点指定一个重儿子，其余儿子称为轻儿子。把轻儿子的贡献预先合并：

$$g_{u,0}=\sum_{v\text{ 是轻儿子}}\max(f_{v,0},f_{v,1}),$$$$g_{u,1}=a_u+\sum_{v\text{ 是轻儿子}}f_{v,0}.$$

若 $h$ 是 $u$ 的重儿子，则

$$f_{u,0}=g_{u,0}+\max(f_{h,0},f_{h,1}),\qquad f_{u,1}=g_{u,1}+f_{h,0}.$$

在“加法为普通加法、乘法为取最大值”的最大加法半环上，上式可以表示为一个 $2\times2$ 矩阵作用于重儿子的状态。沿一条重链从上到下依次相乘，就能得到链顶子树的两个 DP 值。矩阵乘法满足结合律，因此可用线段树维护每条重链区间的乘积。

处理一次点权修改

修改节点 $x$ 的权值只会直接改变 $g_{x,1}$，所以先修改 $x$ 对应的矩阵。此后重新查询 $x$ 所在重链的矩阵乘积，便可得到该链链顶的新旧 DP 值。

若链顶不是根，它作为父节点的一个轻儿子，只会改变父节点的两项轻儿子贡献：

• $g_{p,0}$ 增加新旧 $\max(f_{top,0},f_{top,1})$ 的差；
• $g_{p,1}$ 增加新旧 $f_{top,0}$ 的差。

据此更新父节点矩阵，再跳到父节点所在重链。每次跳跃都跨过一条轻边，重链剖分保证这样的跳跃次数为 $O(\log n)$；每次矩阵单点修改和区间查询又是 $O(\log n)$，故一次权值修改的复杂度为 $O(\log^2 n)$。

证明

静态转移恰好枚举了每个节点“选或不选”的两种状态：选择父节点时禁止选择儿子，不选择父节点时儿子可取较优状态，因此它给出每棵子树的最优独立集。

重链矩阵只是把同一转移按重儿子和轻儿子重新分组，没有改变任何状态含义。线段树维护的矩阵乘积等于从链尾到链顶逐点应用这些转移，所以查询结果就是链顶真实的两个 DP 值。

一次修改后，只有包含修改点的重链乘积先发生变化；该链对更高层的影响只通过链顶作为轻儿子的两项贡献传递。逐条向根更新恰好覆盖全部受影响的祖先链，且不会改变其他子树。因此更新结束后根节点的两个状态均与当前权值一致，二者最大值就是所求答案。

复杂度

预处理为 $O(n)$，每次修改为 $O(\log^2 n)$，总时间复杂度为 $O(n+m\log^2 n)$。线段树、树结构和剖分数组共使用 $O(n)$ 空间。