103296: [Atcoder]ABC329 G - Delivery on Tree

Problem Statement

You are given a binary tree with $N$ vertices. The vertices are numbered $1$ to $N$, with vertex $1$ being the root. The $i$-th edge $(1\leq i \leq N-1)$ connects vertex $i+1$ and vertex $P_i\ (\leq i)$ bidirectionally.

There are one basket and $M$ balls on this tree. The balls are numbered $1$ to $M$, and each ball $j$ has a designated start vertex $S_j$ and goal vertex $T_j$. Initially, the basket is empty and placed at vertex $1$, and the balls are placed at their respective start vertices.

You can perform the following operation any number of times in any order.

• Let $v$ be the current vertex where the basket is placed. Do one of the following:
  • Choose one edge connected to vertex $v$, and move the basket along that edge to the adjacent vertex. The balls inside the basket move together with it.
  • Choose a ball with the start vertex $v$ that is still placed at $v$, and put it into the basket. This operation can only be performed if the basket contains fewer than $K$ balls (that is, the basket cannot contain $K+1$ or more balls).
  • Choose a ball with the goal vertex $v$ from the basket and take it out, placing it at vertex $v$.

A sequence of operations is called a good operation sequence if and only if the basket is eventually empty and placed at vertex $1$, and the balls are eventually placed at their respective goal vertices.

Since it is tiring to move the basket many times, the basket's movement path should traverse each edge exactly twice before returning to vertex $1$. Find the number, modulo $998244353$, of those paths such that a good operation sequence exists following that path.

Constraints

• $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$
• For every $v\ (1\leq v \leq N)$, there are at most two $i$'s such that $P_i=v$.
• $1\leq S_j, T_j \leq N$
• $S_j \neq T_j$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the number, modulo $998244353$, of paths traversing every edge exactly twice before returning to vertex $1$ such that a good operation sequence exists following that path.

Sample Input 1

5 2 1
1 1 3 3
2 4
5 3

Sample Output 1

1

The given graph is shown in the figure below. The circles and squares written next to the vertices represent the start and goal vertices of the balls, respectively.

Among the paths where every edge is traversed exactly twice before returning to vertex $1$, there is only one path such that a good operation sequence exists following that path, which is shown below:

Here, you can construct the following good operation sequence:

1. Move the basket to vertex $2$.
2. Put ball $1$ into the basket.
3. Move the basket to vertex $1$.
4. Move the basket to vertex $3$.
5. Move the basket to vertex $4$.
6. Take ball $1$ out of the basket and place it at vertex $4$.
7. Move the basket to vertex $3$.
8. Move the basket to vertex $5$.
9. Put ball $2$ into the basket.
10. Move the basket to vertex $3$.
11. Take ball $2$ out of the basket and place it at vertex $3$.
12. Move the basket to vertex $1$.

Sample Input 2

5 2 2
1 1 3 3
2 4
5 3

Sample Output 2

2

The value of $K$ has increased by $1$ from Sample Input 1. This allows you to construct a good operation sequence for the following path, in addition to the one illustrated above.

Sample Input 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

Sample Output 3

8

问题描述

给你一个有$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$。

约束

• $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$
• 所有输入值为整数。

输入

输入从标准输入中给出，格式如下：

$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

给出的图如下所示。顶点旁边的圆圈和正方形分别表示球的起点和目标顶点。

在回到顶点$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

5 2 2
1 1 3 3
2 4
5 3

样例输出 2

2

从样例输入 1 中，$K$的值增加了$1$。这使得你可以为以下路径构建一个好操作序列，除了上面示例中的路径之外。

样例输入 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