Hash on Tree 题解

思路

一、直接重算

由于题目保证父亲编号小于儿子编号，所以每次修改后按 $N,N-1,\ldots,1$ 的顺序重新计算所有 $f$ 即可。一次修改需要 $O(N)$ 时间，总复杂度为 $O(NQ)$，适用于第一个子任务。

二、两个特殊结构

若整棵树是一条链，则每个非叶顶点都只有一个儿子，递推式变为 $f(i)=A_i+f(i+1)$，根的答案就是所有 $A_i$ 的和。维护这个和即可在 $O(1)$ 时间内完成一次修改。

若树深和每个顶点的儿子数都不超过 $20$，一次修改只会影响被修改点及其祖先。沿父亲链向上逐点重新枚举儿子计算乘积，一次修改至多需要 $O(20\times20)$ 次模运算。

做法

三、重链上的仿射函数

对原树进行重链剖分。记 $h(v)$ 为 $v$ 的重儿子，$L(v)$ 为 $v$ 的所有轻儿子。定义

把顶点 $v$ 看成仿射函数

若 $v$ 有重儿子，则 $f(v)=g_v(f(h(v)))$；若 $v$ 没有重儿子，把链尾之后的值看成 $0$，仍有 $f(v)=g_v(0)=A_v$。因此，一条从链头到链尾的重链所对应的 $f$ 值，就是按从上到下的顺序复合所有 $g_v$ 后在 $0$ 处的取值。

仿射函数 $(a,b)$ 表示 $ax+b$。若上方函数为 $(a_1,b_1)$、下方函数为 $(a_2,b_2)$，复合结果为

这个运算满足结合律，所以可用一棵线段树维护重链剖分序中的所有仿射函数，并查询任意整条重链的复合结果。

四、维护轻儿子乘积

当某个顶点的权值改变时，它所在重链的链头 DP 值可能改变。若该链头不是根，它必定是其父亲的轻儿子，于是父亲的 $P_v$ 也要改变，继而影响父亲所在重链。沿这样的轻边向上跳，次数为 $O(\log N)$。

需要特别处理因子为 $0$ 的情况，不能直接用模逆元删除旧因子。可以把所有轻儿子的 DP 值按父亲分组放进另一棵乘积线段树：每个轻儿子占一个位置，每个父亲拥有一个连续区间，其区间乘积就是 $P_v$。这样单个轻儿子变化与重新取得父亲的乘积都需要 $O(\log N)$，并天然支持零值。

每次跨越一条轻边时，需要常数次仿射线段树查询、仿射点修改、乘积点修改和乘积区间查询。

五、正确性证明

首先，对任意顶点 $v$，轻儿子的贡献恰为 $P_v$。若存在重儿子 $h(v)$，所有儿子的乘积等于 $P_vf(h(v))$，故递推式等于 $g_v(f(h(v)))$；若不存在重儿子，$v$ 是叶子，令链尾外参数为 $0$ 后同样得到 $A_v$。

其次，由上到下复合一条重链上的函数，逐层代入的结果与原递推完全相同，所以链头的 DP 值等于该复合函数在 $0$ 处的值。

最后，一次点修改只直接改变对应顶点的仿射函数。链内影响由函数合成自动传到链头；链头若改变，只会作为一个轻儿子改变父亲的轻儿子乘积。不断处理父亲所在重链，直到根链，恰好覆盖且只覆盖所有可能变化的位置。因此最终得到的根链值就是修改后的 $f(1)$。

综上，算法始终输出正确的树哈希值。

复杂度

预处理复杂度为 $O(N\log N)$。每次修改至多跨越 $O(\log N)$ 条轻边，每一步执行 $O(\log N)$ 的线段树操作，因此单次修改复杂度为 $O(\log^2 N)$。空间复杂度为 $O(N)$。