AT_abc329_g [ABC329G] Delivery on Tree

题目描述

给定一棵有 $N$ 个顶点的二叉树。顶点编号为 $1$ 到 $N$，顶点 $1$ 是根。第 $i$ 条边（$1\leq i\leq N-1$）连接顶点 $i+1$ 和顶点 $P_i$（$P_i\leq i$），为双向边。

在这棵树上有 $1$ 个篮子和 $M$ 个球。球编号为 $1$ 到 $M$，对于每个球 $j$，给定其起始顶点 $S_j$ 和目标顶点 $T_j$。最初，篮子为空，放在顶点 $1$，每个球放在其起始顶点。

你可以任意次数、任意顺序地进行以下操作：

• 设当前篮子在顶点 $v$，可以进行以下任一操作：
  • 选择与顶点 $v$ 相连的一条边，沿该边将篮子移动到相邻顶点。此时，篮子中的所有球也会一起移动。
  • 如果有起始顶点为 $v$ 且当前还在起始顶点的球，可以选择其中一个放入篮子。只有当篮子中球的数量小于 $K$ 时才能进行此操作（即篮子中不能有 $K+1$ 个或更多的球）。
  • 如果有目标顶点为 $v$ 且当前在篮子中的球，可以选择其中一个从篮子中取出，放到顶点 $v$ 上。

当所有操作结束时，若篮子为空且在顶点 $1$，每个球都在其目标顶点，则称该操作序列为良好操作序列。

由于频繁移动篮子很累，因此希望篮子的移动路径限定为：每条边恰好经过 $2$ 次，并最终回到顶点 $1$。在所有满足此条件的路径中，问有多少种路径可以使得存在良好操作序列。请输出该数量对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $K$ $P_1$ $P_2$ $\dots$ $P_{N-1}$ $S_1$ $T_1$ $S_2$ $T_2$ $\vdots$ $S_M$ $T_M$

输出格式

请输出所有满足条件的路径数对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

5 2 1
1 1 3 3
2 4
5 3

输出 #1

1

输入输出样例 #2

输入 #2

5 2 2
1 1 3 3
2 4
5 3

输出 #2

2

输入输出样例 #3

输入 #3

15 4 2
1 2 1 4 2 3 4 7 3 7 5 9 11 8
14 12
5 4
13 15
5 12

输出 #3

8

说明/提示

限制条件

• $2\leq N\leq 10^4$
• $1\leq M\leq 2\times 10^5$
• $1\leq K\leq 10^3$
• $1\leq P_i\leq i$
• 对于所有 $v$（$1\leq v\leq N$），满足 $P_i=v$ 的 $i$ 的个数至多为 $2$
• $1\leq S_j, T_j\leq N$
• $S_j\neq T_j$
• 所有输入均为整数

样例解释 1

给定的图如下图所示。顶点旁的圆和方块分别表示该编号球的起始顶点和目标顶点。

在所有每条边恰好经过 $2$ 次并回到顶点 $1$ 的路径中，只有下图所示的路径可以使得存在良好操作序列。

具体来说，可以按如下顺序操作：

1. 将篮子移动到顶点 $2$。
2. 将球 $1$ 放入篮子。
3. 将篮子移动到顶点 $1$。
4. 将篮子移动到顶点 $3$。
5. 将篮子移动到顶点 $4$。
6. 将球 $1$ 从篮子中取出，放到顶点 $4$。
7. 将篮子移动到顶点 $3$。
8. 将篮子移动到顶点 $5$。
9. 将球 $2$ 放入篮子。
10. 将篮子移动到顶点 $3$。
11. 将球 $2$ 从篮子中取出，放到顶点 $3$。
12. 将篮子移动到顶点 $1$。

样例解释 2

与样例 1 相比，$K$ 的值增加了 $1$。因此，除了上述路径外，还可以通过下图所示的路径构成良好操作序列。

由 ChatGPT 4.1 翻译