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$ 取模的结果。
说明/提示
## 限制条件
- $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 翻译