G - Delivery on Tree Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 625 点

問題文

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 に繋がる辺を 1 つ選び、カゴをその辺に沿って動かして隣接する頂点に移動させる。 このとき、カゴの中に入っているボールも一緒に移動する。
    • スタート頂点が v であり、今もスタート頂点に置かれているようなボールを 1 つ選んで、カゴの中に入れる。 この操作は、元々カゴの中に入っているボールが K 個未満である場合にのみ行える（すなわち、カゴの中に K+1 個以上のボールを入れることはできない）。
    • ゴール頂点が v であり、今カゴの中に入っているようなボールを 1 つ選んでカゴから取り出し、頂点 v に置く。

全ての操作が終了した時点で、カゴは空の状態で頂点 1 に置かれており、ボールはそれぞれのゴール頂点に置かれているような操作列を良い操作列と呼びます。

カゴを何度も動かすのは疲れるので、カゴが動く経路は、全ての辺をちょうど 2 回ずつ通り頂点 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) について、P_i=v を満たす i の数は高々 2 個
  • 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

出力

全ての辺をちょうど 2 回ずつ通り頂点 1 に戻ってくるような経路のうち、その経路に従ってカゴを動かす良い操作列が存在するようなものの数を 998244353 で割った余りを出力せよ。

入力例 1

5 2 1
1 1 3 3
2 4
5 3

出力例 1

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 に動かす。

入力例 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

Score : 625 points

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