Delivery on Tree

题目描述

给定一棵有 $N$ 个顶点的二叉树。顶点编号为 $1$ 到 $N$，顶点 $1$ 为根。第 $i$ 条边 $(1\leq i \leq N-1)$ 双向连接顶点 $i+1$ 和 顶点 $P_i\ (\leq i)$。 树上有一个篮子和 $M$ 个球。球编号为 $1$ 到 $M$，每个球 $j$ 有一个指定的起始顶点 $S_j$ 和目标顶点 $T_j$。初始时，篮子为空并放在顶点 $1$，球放在各自的起始顶点上。 你可以任意次数按任意顺序执行下列操作。

令 $v$ 为当前篮子所在的顶点。执行以下三项之一： 选择一条与顶点 $v$ 相连的边，沿该边移动篮子到相邻的顶点。篮子内的球随篮子一起移动。 选择一个起始顶点为 $v$ 且仍放置在 $v$ 的球，并把它放入篮子。此操作只能在篮子中球的数量少于 $K$ 时执行（即篮子中不能包含 $K+1$ 个或更多球）。 从篮子中选择一个目标顶点为 $v$ 的球并把它取出，放置在顶点 $v$。

当且仅当篮子最终为空并放回顶点 $1$，且球最终被放置在它们各自的目标顶点时，称该操作序列为可行操作序列。 由于频繁移动篮子很费力，篮子的移动路径应在返回顶点 $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$

输出格式

输出满足存在沿该路径执行的可行操作序列的、在返回顶点 $1$ 之前恰好遍历每条边两次的路径数量，对 $998244353$ 取模。

5 2 1
1 1 3 3
2 4
5 3

1

5 2 2
1 1 3 3
2 4
5 3

2

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

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)$，至多有两个 $i$ 满足 $P_i=v$。 $1\leq S_j, T_j \leq N$ $S_j \neq T_j$ 所有输入值均为整数。下图展示了给定的图。顶点旁的圆圈和方块分别表示球的起始顶点和目标顶点。 在每条边被恰好遍历两次并返回顶点 $1$ 的路径中，只有一条路径存在沿该路径执行的可行操作序列，如下所示： 这里，你可以构造如下的可行操作序列：

将篮子移动到顶点 $2$。 把球 $1$ 放入篮子。 将篮子移动到顶点 $1$。 将篮子移动到顶点 $3$。 将篮子移动到顶点 $4$。 将球 $1$ 从篮子中取出并放在顶点 $4$。 将篮子移动到顶点 $3$。 将篮子移动到顶点 $5$。 把球 $2$ 放入篮子。 将篮子移动到顶点 $3$。 将球 $2$ 从篮子中取出并放在顶点 $3$。 将篮子移动到顶点 $1$。

从样例输入 1 中 $K$ 的值增加了 $1$。这使得除了上图所示的路径之外，你还能为下面的路径构造可行操作序列。

标签: AtCoder|abc329G

来源

AtCoder|abc329G