P4338 历史笔记

神题啊！神题（赞叹）

形式化题意

给定一棵 $n$ 个点的树，第 $i$ 个点有点权 $a_i$。且每个点都有颜色，初始时颜色都为 $1$，第 $i$ 个点的颜色是 $c_i$。

你可以对一个点 $x$ 进行一次操作：

1. 计数有多少 $v$，满足 $v$ 在 $x \to 1$ 的路径（包含 $x$ 和 $1$）上，且 $c_v \ne x$。
   将满足条件的 $v$ 的个数记作 $cnt$，并使 $ans := ans + cnt$，初始时 $ans = 0$。
2. 将 $x \to 1$ 路径上的点颜色全部变为 $x$。

现在知道了第 $i$ 个点总共被操作 $a_i$ 次，问如何安排 $\sum a$ 次操作，使最后 $ans$ 最大。然后还有 $m$ 个询问，每次如下：

• x w 表示将 $a_x := a_x + w$ 后的答案。

题解

第一步就是一个比较难的性质的观察：每个点对答案的贡献是相互独立的。这里每个点对答案的贡献是指，它被其它点当做不同颜色计数，被算了几次。

有了这个观察后，可以分别对每个点 $x$ 算出答案。具体的方法为，假设现在有一个序列 $b$，长度为 $k$（$k = $ $x$ 的子树大小），有 $c_1$ 个 $b_1$，$c_2$ 个 $b_2$，$\cdots$，$c_k$ 个 $b_k$。
这里序列 $b$ 就是 $x$ 子树点集，$c_{x} = a_{b_x}$。然后等同于安排 $b$ 的顺序，使得最后长度为 $\sum c$ 的序列中，相邻的不同颜色的元素最大化。

根据一个类似于摩尔投票法的证明，有一个这样的结论，设 $T = \sum\limits_{i = 1}^k c_i, M = \max\limits_{i = 1}^k c_i$：答案是 $\min\{T - 1, 2(T - M)\}$。

现在转化完了之后，题目变成了求：

$$\sum\limits_{i = 1}^n \min\{T_i - 1, 2(T_i - M_i)\}$$

每次询问 x w 变为对 $1 \to x$ 链上的点的 $T_i$ 增加 $w$，再设法改变一下 $M_i$，这就是 $\mathcal{O}(nq)$ 暴力。

到这里获得了整整 $30$ 分的好成绩。接下来再接再厉，考虑优化这个暴力。

又是一步重要的观察：任意时刻，任何被非 $1$ 的颜色染色的结点所形成的联通块，一定是一条直上直下的链。

这使得 $M_i$ 所代表的颜色，也一定是一条直上直下的链。

这个性质让我们回想起了树点涂色，提示我们可以用 $\text{LCT}$ 解决此题。

同样的，根据上面的式子的分界线，我们将每个边归为重边和轻边，定义为：

• 重边：若 $2T_i \geqslant T_{fa_i} + 1$，则 $(i, fa_i)$ 为重边。
• 轻边：不满足该边为重边的边。

由于 $T_{fa_i} = \sum\limits_{j \in fa_i.\text{son}} T_j$，所以每个点往儿子连的重边显然不会超过 $1$ 个。

一次 $a_x := a_x + w$ 影响到的点，一定是 $x \to 1$ 上的点，考虑讨论重边在操作后的变化。

假设现在正在 access 中，讨论 $(x, fa_x)$ 这条边的轻重：

• 如果 $(x, fa_x)$ 操作前是重边，那么一定该边仍是重边，可以轻松用糖水不等式证明。
• 如果 $(x, fa_x)$ 操作前是轻边，那么有可能 $fa_x$ 的原重边改为 $(x, fa_x)$ 这条边；也有可能 $fa_x$ 的重边消失，只剩轻边。

综上所述，遇到重边可以直接跳上去，因为这个不会影响答案（$T_x - M_x$ 不变）。

时间复杂度为跳轻边的次数，类似重链剖分的复杂度分析，单次 access 复杂度是 $\mathcal{O}(\sum a)$ 的。（每次跳轻链使 $T_x$ 翻倍）