T1 - Output Only 题解
题目简述
题目大意：
给定一棵 $N$ 个节点的有根树，根为 1。每个节点有一个初始颜色 $c_i \in [0, k-1]$。
操作：选择一个节点 $u$ 和颜色 $p$，将 $u$ 及其子树内所有节点的颜色 $c_v \leftarrow (c_v + p) \pmod k$。
目标：通过若干次操作，使所有节点颜色变为 0。题目要求在发生 $Q$ 次单点颜色修改 $(w_i, x_i)$ 后，分别求出达成目标所需的最少操作次数。
- $N, Q, k \le 2 \times 10^5$
The Key：利用 差分 的思想，将子树修改转化为对“父子颜色关系”的维护。这是一个典型的树上差分或转化贡献维度的思维题。
子任务分析
Subtask 1：树是一条链
当树是一条链（例如 $1 \to 2 \to \dots \to N$）时，我们可以利用序列差分的思想。定义 $d_i = (c_i - c_{i-1}) \pmod k$，其中 $c_0 = 0$。
对于以 $u$ 为根的子树（链上的后缀）进行操作，只会改变 $d_u$ 的值，而不会影响 $d_{u+1} \dots d_N$。为了让所有 $c_i = 0$，等价于让所有差分值 $d_i = 0$。如果某位置 $d_i \neq 0$，我们就必须在 $i$ 处进行一次操作来修正它。因此答案为 $\sum_{i=1}^N [d_i \neq 0]$。
时间复杂度：$\mathcal{O}(N + Q)$
Subtask 2：$k=2$
当只有两种颜色时，问题可以简化为统计 坏边。考虑一条边 $(u, v)$，其中 $u$ 是 $v$ 的父节点。
如果在 $v$ 处不进行任何操作，那么 $v$ 的颜色变化量将完全取决于 $u$ 的变化量。即操作后 $c'_v - c'_u \equiv c_v - c_u \pmod k$。要使最终 $c'_v = c'_u = 0$，必须满足 $c_v - c_u \equiv 0$。如果初始 $c_v \neq c_u$，我们就必须在 $v$ 处进行一次操作。对于 $k = 2$，这等价于统计两端颜色不同的边数（根节点视作父节点颜色为 0）。
Subtask 4：$N, Q \le 5 \times 10^4$
对于一般情况，可以考虑 根号分治：
- 按照节点的度数 $\deg$ 分为大点和小点。
- 修改小点时，直接暴力遍历其所有相邻边，更新答案。
- 修改大点时，更新大点的信息，维护大点与大点之间的关系。
时间复杂度：$\mathcal{O}(Q\sqrt{N})$
正解思路
根据上述性质探索，我们可以得到核心结论：
........................................................................该题解待审
........................................................................(剩余 2697 个中英字符)