这是使用 GPT 5.5 Thinking Xhigh 翻译的官方题解。

子任务 1

当 $n=3$ 时：

• 若所有边都处于激活状态，答案为 $k(k-1)$。
• 否则答案为 $k$。

子任务 2

设 $\Gamma_i$ 为包含边 $l_i\to l_{i+1}$ 的面，其中 $1\le i<m$；设 $\Gamma_0$ 为包含边 $l_m\to l_1$ 的面。

可以先给 $\Gamma_0$ 染色，有 $k$ 种方法。然后给 $\Gamma_1$ 染色，此时有 $k-1$ 种颜色可用。继续按 $\Gamma_2,\ldots,\Gamma_m$ 的顺序染色时，每个新面都需要避开两个已经相邻的颜色，因此有 $k-2$ 种选择。

所以答案为：

• 当 $n=3$ 时，答案为 $k$。
• 当 $n\ge 5$ 时，答案为 $k(k-1)(k-2)^{(n-5)/2}$。

子任务 3

若所有边都未激活，则答案为 $k$。

否则，设激活边数为 $x$，这些边会把若干面合并成 $x$ 个面，并且它们按环相邻。于是问题变成：给一个环上的 $x$ 个点染色，相邻点颜色不同，求方案数。

可以用动态规划计算。定义：

• $\operatorname{dp1}_i$：给 $i$ 个面染色，要求相邻面颜色不同，并且第一个面与最后一个面颜色也不同的方案数。
• $\operatorname{dp2}_i$：给 $i$ 个面染色，要求相邻面颜色不同，但第一个面与最后一个面颜色相同的方案数。

初始为 $\operatorname{dp1}_1=0,\operatorname{dp2}_1=k$。转移为：

• $\operatorname{dp1}_i=\operatorname{dp1}_{i-1}(k-2)+\operatorname{dp2}_{i-1}(k-1)$。
• $\operatorname{dp2}_i=\operatorname{dp1}_{i-1}$。

子任务 4 至 5

这些子任务可以用暴力通过。例如，作者的做法复杂度为 $O((q+1)(n^3+k^n n))$，大致如下：

1. 显式构建原图中面的邻接图。
2. 使用 Floyd-Warshall 算法判断哪些面会被合并到同一个面中。
3. 枚举原始面的所有 $k^n$ 种染色，并逐一检查是否合法。

子任务 6

这一子任务只需要注意一个性质：

• 如果树中存在奇度数顶点，答案为 $0$。
• 否则答案为 $2$。

子任务 7

记 $\chi(n)$ 表示用 $k$ 种颜色给 $n$ 个按环相邻的面染色的方案数。

将子任务 2 和子任务 3 的思想结合。先给覆盖整棵树上方的外侧面 $\Gamma_0$ 染色，然后按照面的嵌套顺序继续染色。对于同一个树上顶点下方的若干面，可以一起处理。

若顶点 $v$ 是根，则需要染色 $\deg v-1$ 个面，对答案贡献 $\chi(\deg v)/k$。

若顶点 $v$ 不是根，则它下方有 $\deg v-2$ 个面，对答案贡献 $\chi(\deg v)/(k(k-1))$。

把所有非叶顶点对应的贡献相乘，即可得到答案。

子任务 8 至 10

称一个顶点 $v$ 为悬挂顶点，当且仅当它不是叶子，并且至多通过一条激活边与其他顶点相连。

删除悬挂顶点不会改变答案。因此，本组子任务的思路是：每个询问独立处理，并尽可能高效地删去所有悬挂顶点。

由于题目中显式给出了父亲数组，且满足 $p_i<i$，可以用两次扫描完成删除：

1. 按 $n,n-1,\ldots,1$ 的顺序遍历顶点。如果顶点 $v$ 是叶子，则它不是悬挂顶点，不删除。否则，当且仅当不存在从编号更大且未被删除的顶点连向 $v$ 的激活边时，删除 $v$。
2. 按 $1,2,\ldots,n$ 的顺序再遍历一次。若顶点 $v$ 是当前连通块的根，也就是它没有通过激活边连向一个未删除的父亲，并且它只有一个儿子，则删除 $v$。

两次扫描之后，树中不再存在悬挂顶点。不过，原树可能被分成多个连通块。

仍然可以按照面的嵌套关系染色。若顶点 $v$ 是某个连通块的根，则它给答案贡献 $\chi(\deg'(v))/k$；其他非叶顶点贡献 $\chi(\deg'(v))/(k(k-1))$。这里 $\deg'(v)$ 表示删除悬挂顶点后的度数。

该做法复杂度为 $O(nq)$。由于实现中主要是两三层顺序循环，没有复杂的跳跃访问，实际运行速度较快。

子任务 11

这一子任务的思路是：把原树压缩到不超过 $4q$ 个顶点，同时答案只差一个常数乘子 $M$。实现细节较复杂，需要处理较多情况，建议配合对拍测试。

首先把边分为两类：

• 恒定边：在所有询问中始终处于激活状态的边。
• 不稳定边：在某次询问中会改变状态的边。

维护数组 $e$，其中 $e(v)$ 表示外层环上有多少个顶点通过恒定边连接到 $v$。初始化时，若 $v$ 是叶子，则 $e(v)=1$；否则 $e(v)=0$。

这样可以不再认为外层环一定经过原树叶子，而是认为它经过一些“虚拟顶点”，这些虚拟顶点的数量已经被记录在 $e(v)$ 中。这个变换不会改变答案。

接着，对每个顶点 $v$ 计算 $\operatorname{minf}(v)$：从 $v$ 沿恒定边向下走，能到达虚拟顶点的最大点不相交路径条数。

然后可以进行如下压缩：

• 找出形如 $v_1\to v_2\to\cdots\to v_l$ 的链，其中相邻顶点之间有边，且中间顶点 $v_2,\ldots,v_{l-1}$ 都恰好有两个邻居。这样的链可以压成一条边。对应地修改询问序列：新边处于激活状态，当且仅当原链上所有边都处于激活状态。

接下来定义支撑顶点：满足 $\operatorname{minf}(v)\ge 2$ 的顶点称为支撑顶点。

若从顶点 $v$ 沿向上的边可以到达某个不同于 $v$ 的支撑顶点，并且 $\operatorname{minf}(v)\ge 1$，则称 $v$ 为可预测顶点。这样的顶点在不断删除悬挂顶点的过程中永远不会被删去。

因此，可以把每个可预测顶点重新挂到虚拟根 $-1$ 下，并将它原父亲 $p$ 的 $e(p)$ 增加 $1$。这不会改变答案。为了方便，把虚拟根 $-1$ 也视为支撑顶点，但它本身不是实际顶点，所以不对答案产生贡献。

如果某个顶点 $v$ 已经挂在 $-1$ 下，并且 $\operatorname{minf}(v)$ 等于它的儿子数量，那么 $v$ 对答案的贡献是常数。可以把这部分贡献乘入 $M$，然后删除 $v$，并把它的所有儿子重新挂到 $-1$ 下。

经过详细分析，这样压缩后剩余顶点数不超过 $4q$。因此本子任务可在 $O(n+q^2)$ 时间内解决。

子任务 12

另一种优化 $O(nq)$ 做法的方式，是利用树高 $h\le 20$。

显式维护删除所有悬挂顶点之后剩下的树。将顶点分成三类：

• $N$ 类：在第一次扫描中被删除的顶点。
• $S$ 类：在第二次扫描中被删除的顶点。
• $P$ 类：不会在算法过程中被删除的顶点。

考虑删除一条边 $v\to p_v$。

首先从 $p_v$ 开始，沿激活边向上走。直到当前顶点还有另一条从下方连入、且连接到 $P$ 类顶点的激活边，或者走到根为止。所有经过的顶点都改为 $N$ 类。

如果停在一个仍有其他连入激活边的顶点处，并且该边是唯一相关边，则继续沿激活边向上处理。

如果停下是因为某个顶点 $u$ 没有向上的激活边，则需要从 $u$ 向下走，直到遇到第一个满足以下条件的顶点：

• 它是叶子。
• 或者它有两个通过激活边连接的 $P$ 类儿子。

沿途经过的顶点标记为 $S$ 类。

如果过程中到达了一个有另一条来自 $P$ 类顶点的激活边的顶点，则不需要继续改变类别。

由于每次都是逐个顶点改变类别，答案也可以同步维护。复杂度为 $O(n+qh)$。

子任务 13 至 15

满分做法有两种思路，复杂度都可以达到 $O(n+q\log n)$，但基于不同原则。

做法一：分治

可以稍微修改子任务 11 的压缩方法，并将其用于分治。额外需要做的是：在每个连通块中，剪去一条稳定或不稳定的向上边，并保证被剪掉的部分只由悬挂顶点构成。

具体流程如下：

1. 先根据当前询问区间压缩树。
2. 将询问序列分成大小接近的两半。
3. 对两半询问分别递归求解。

也就是说，每一层递归都先针对当前询问区间压缩树，再继续分治。由于一个包含 $q$ 个询问的区间对应的压缩树大小为 $O(q)$，所以总复杂度为 $O(q\log q)$。

做法二：数据结构

第二种做法基于动态维护压缩树，压缩树只保留仍处在 $P$ 类中的顶点。

原题解就写到这里了，后面没了。