树上配送

题目描述

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

这棵树上有一个篮子和 $M$ 个球。球编号为 $1$ 到 $M$,每个球 $j$ 都指定了起点 $S_j$ 和终点 $T_j$。初始时,篮子为空并放置在顶点 $1$,球分别放在各自的起点上。

你可以任意多次、以任意顺序进行以下操作。

设当前篮子所在的顶点为 $v$,执行以下任一操作:

• 选择一条与顶点 $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$

输出格式

输出所有边恰好经过 $2$ 次并回到顶点 $1$ 的路径中,存在沿该路径移动篮子的好操作序列的路径条数对 $998244353$ 取模的结果。

样例

5 2 1
1 1 3 3
2 4
5 3

1

在所有边恰好经过 $2$ 次并回到顶点 $1$ 的路径中,存在沿该路径移动篮子的好操作序列的路径只有 $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$。

5 2 2
1 1 3 3
2 4
5 3

2

与样例 1 相比,$K$ 的值增加了 $1$。因此,除上述路径外,还有 $1$ 条路径也能构造出好操作序列。

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 \le N \le 10^4$
• $1 \le M \le 2\times 10^5$
• $1 \le K \le 10^3$
• $1 \le P_i \le i$
• 对所有 $v\ (1 \le v \le N)$,满足 $P_i = v$ 的 $i$ 至多有 $2$ 个
• $1 \le S_j, T_j \le N$
• $S_j \neq T_j$
• 输入均为整数