Score : $625$ points

问题描述

给定一棵包含 $N$ 个顶点的二叉树。顶点编号从 $1$ 到 $N$，其中顶点 $1$ 是根节点。第 $i$ 条边 $(1\leq i \leq N-1)$ 双向连接顶点 $i+1$ 和顶点 $P_i\ (\leq i)$。

在这个树上有 $1$ 个篮子和 $M$ 个球。球的编号为 $1$ 到 $M$，每个球 $j$ 有一个指定的起点 $S_j$ 和终点 $T_j$。初始时，篮子为空并放置在顶点 $1$ 处，球则放置在其各自的起点处。

你可以按任意顺序执行以下操作任意多次：

• 让 $v$ 表示当前篮子所在的顶点，执行以下任一操作：
  • 选择一条与顶点 $v$ 相连的边，沿该边移动篮子至相邻顶点。篮子中的球随之一起移动。
  • 选择一个起点为 $v$ 并且仍在顶点 $v$ 上的球，将其放入篮子中。此操作仅当篮子中球的数量少于 $K$ 个（即篮子不能容纳 $K+1$ 或更多的球）时才能执行。
  • 从篮子中选择一个终点为 $v$ 的球取出，并将其放在顶点 $v$ 处。

如果最终篮子为空并且位于顶点 $1$ 处，同时所有球都到达了它们各自的终点，则称这样的操作序列是一个有效操作序列。

由于频繁移动篮子很费力，篮子的移动路径应在返回顶点 $1$ 之前恰好经过每条边两次。求满足存在遵循该路径的有效操作序列的路径数量模 $998244353$ 的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:55:10