#P15864. [Roi2026]好染色-8

    ID: 15075 传统题 2000ms 1024MiB 尝试: 3 已通过: 2 难度: 10 上传者: 标签>CF3300NOI/NOI+/CTS平面图对偶顶点着色树形 DP递推计数模逆元离线查询分治算法

[Roi2026]好染色-8

题目描述

伊尔达尔决定从事抽象艺术。他以一棵有根树作为画作基础。树有 nn 个顶点,编号为 11 到 nn,其中顶点 11 是根。

根没有父亲;对于任意其他顶点 u≥2u\ge 2,从 uu 到根的路径上的第一个顶点称为 uu 的父亲,记为 pup_u。父亲为 vv 的顶点称为 vv 的儿子。没有儿子的顶点称为叶子。保证根至少有两个儿子。

对这棵树进行深度优先遍历:先访问根,然后按顺序递归访问其各个儿子的子树。树中顶点已经按照这次 DFS 的访问顺序编号。因此,对于任意顶点 ii,它的子树中所有顶点的编号构成一段连续整数。

设树中共有 mm 个叶子。伊尔达尔按编号递增顺序写下这些叶子的编号,得到

l1<l2<⋯<lm。l_1<l_2<\cdots<l_m。

然后他添加边连接所有形如 (lj,lj+1)(l_j,l_{j+1}) 的叶子对,并额外连接 lml_m 与 l1l_1。添加得到的环

l1→l2→⋯→lm→l1l_1\to l_2\to\cdots\to l_m\to l_1

称为外环。

伊尔达尔把所得图画在平面上:外环画成一个圆,叶子 l1,l2,…,lml_1,l_2,\ldots,l_m 按逆时针方向位于圆周上,相邻叶子之间的圆弧表示外环的边。树中其他顶点画在圆内,树边画成连接顶点的线段,各条边的内部互不相交。只考虑外环内部的面,不给外部的无界区域染色。

这样,外环内部的平面区域被图划分成 mm 个区域,这些区域称为面。若两个不同的面有公共边,则称它们相邻。

例如,下图的树有 5 个叶子,外环内部被划分为 5 个面。

平面图及五个面

相邻面为 (Γ1,Γ2)(\Gamma_1,\Gamma_2)、(Γ1,Γ5)(\Gamma_1,\Gamma_5)、(Γ2,Γ3)(\Gamma_2,\Gamma_3)、(Γ2,Γ4)(\Gamma_2,\Gamma_4)、(Γ2,Γ5)(\Gamma_2,\Gamma_5)、(Γ3,Γ4)(\Gamma_3,\Gamma_4)、(Γ4,Γ5)(\Gamma_4,\Gamma_5)。

为了完成画作,伊尔达尔计划把每个面染成 kk 种颜色之一。若任意相邻的两个面颜色不同,则称染色是正确的。他把一幅图的势能定义为正确染色方案数对 109+710^9+7 取模后的结果。

在计算初始图的势能后,伊尔达尔会进行 qq 次操作。第 ii 次操作给出一个数 viv_i,作用在连接 viv_i 与 pvip_{v_i} 的树边上:

  • 如果这条边当前画在图中,则将它从图中删除;
  • 如果这条边当前不在图中,则将它重新画出。

每次改变后,图中的面可能发生变化:删除一条边可能使两个面合并,重新画出一条边可能把一个面分成两个面。

例如,若在上图中删除边 8−98-9,则面 Γ4\Gamma_4 与 Γ5\Gamma_5 合并为一个面 Γ4+5\Gamma_{4+5};此时相邻面为 (Γ1,Γ2)(\Gamma_1,\Gamma_2)、(Γ1,Γ4+5)(\Gamma_1,\Gamma_{4+5})、(Γ2,Γ3)(\Gamma_2,\Gamma_3)、(Γ2,Γ4+5)(\Gamma_2,\Gamma_{4+5})、(Γ3,Γ4+5)(\Gamma_3,\Gamma_{4+5})。

只有两个叶子时,外环中的两条圆弧视为两条不同的边。删除某条树边后,如果它两侧已属于同一个面,则不会产生新的染色限制。

在初始状态以及每次操作后,都需要求出当前图的势能。

输入格式

第一行包含一个整数 tt(1≤t≤100001\le t\le 10000),表示测试数据组数。

接下来依次给出 tt 组数据。

每组数据第一行包含三个整数 n,k,qn,k,q:

$$3\le n\le 10^6, \qquad 2\le k\le 10^9, \qquad 0\le q\le 300\,000。$$

第二行包含 p2,p3,…,pnp_2,p_3,\ldots,p_n,其中 pip_i 是顶点 ii 的父亲,满足

1≤pi<i。1\le p_i<i。

保证顶点编号为 DFS 顺序,并且在 p2,p3,…,pnp_2,p_3,\ldots,p_n 中,数值 11 至少出现两次,即根至少有两个儿子。

接下来 qq 行,第 ii 行包含一个整数 viv_i(2≤vi≤n2\le v_i\le n),表示第 ii 次操作切换树边 (vi,pvi)(v_i,p_{v_i}) 的存在状态。

保证所有测试数据中 nn 的总和不超过 10610^6,qq 的总和不超过 300000300000。

输出格式

对每组数据,输出 q+1q+1 个数:

  • 第一个数为初始图的势能;
  • 接下来第 ii 个数为执行第 ii 次操作后的势能。

这些整数可以用空格或换行分隔。

样例

2
3 4 5
1 1
2
3
2
3
3
9 4 8
1 2 2 1 5 5 1 8
9
8
3
5
4
3
9
8
12
4
4
4
12
4
96
48
48
24
12
12
12
12
36

子任务与评分

树的高度定义为从根到其他顶点的简单路径中,边数的最大值。

子任务 分值 附加限制 必要子任务
1 6 n=3, k≤4, q≤10, t≤100, p2=p3=1n=3,\ k\le 4,\ q\le 10,\ t\le 100,\ p_2=p_3=1 -
2 9 $\sum n\le 1000,\ q=0,\ p_i=2\lfloor i/2\rfloor-1,\ n$ 为奇数
3 10 ∑n≤1000,∑q≤1000, pi=1\sum n\le 1000,\sum q\le 1000,\ p_i=1 1
4 n≤9, k≤4, q=0, t≤100n\le 9,\ k\le 4,\ q=0,\ t\le 100 -
5 3 n≤9, k≤4, q≤10, t≤100n\le 9,\ k\le 4,\ q\le 10,\ t\le 100 样例,4
6 2 ∑n≤1000, k=2, q=0\sum n\le 1000,\ k=2,\ q=0 -
7 11 ∑n≤1000, q=0\sum n\le 1000,\ q=0 2,4,6
8 15 ∑n≤1000,∑q≤1000\sum n\le 1000,\sum q\le 1000 样例,1-7
9 4 ∑n≤5000,∑q≤5000\sum n\le 5000,\sum q\le 5000 样例,1-8
10 3 ∑n≤10000,∑q≤10000\sum n\le 10000,\sum q\le 10000 样例,1-9
11 6 ∑n≤100000,∑q≤5000\sum n\le 100000,\sum q\le 5000
12 7 ∑n≤100000,∑q≤100000\sum n\le 100000,\sum q\le 100000,树高不超过 2020 样例,1,4,5
13 14 ∑n≤100000,∑q≤100000\sum n\le 100000,\sum q\le 100000 样例,1-12
14 3 ∑n≤300000,∑q≤300000\sum n\le 300000,\sum q\le 300000 样例,1-13
15 ∑n≤1000000,∑q≤300000\sum n\le 1000000,\sum q\le 300000 样例,1-14

评测说明

每个子任务内的全部测试点通过后,才能获得该子任务的分数;还需通过表中列出的必要子任务。「样例」或「题面测试」指子任务 0。