E - Red and Blue Tree 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

N 頂点の木と、長さ M の数列 A=(A_1,\ldots,A_M)、整数 K が与えられます。
木の頂点には 1 から N の番号がつけられており、i 番目の辺は頂点 U_i と V_i を結んでいます。

この木の N-1 個の辺をそれぞれ赤か青のどちらかに塗ります。そのような方法は 2^{N-1} 通りありますが、そのうち次の条件を満たすような塗り方の個数を 998244353 で割った余りを求めてください。

条件：
最初、駒を頂点 A_1 におく。i=1,\ldots,M-1 の順に、駒を頂点 A_i から頂点 A_{i+1} まで、辺をたどって最短経路で動かす。 これらの操作を最後まで行ったとき、赤く塗られた辺を通過した回数を R、青く塗られた辺を通過した回数を B とすると、R-B=K である。

制約

  • 2 \leq N \leq 1000
  • 2 \leq M \leq 100
  • |K| \leq 10^5
  • 1 \leq A_i \leq N
  • 1\leq U_i,V_i\leq N
  • 与えられるグラフは木である
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M K
A_1 A_2 \ldots A_M
U_1 V_1
\vdots
U_{N-1} V_{N-1}

出力

答えを出力せよ。

入力例 1

4 5 0
2 3 2 1 4
1 2
2 3
3 4

出力例 1

2

1,3 番目の辺を赤く、2 番目の辺を青く塗ったとき、

  • 頂点 2 から頂点 3 への移動で赤い辺を 0 回、青い辺を 1 回
  • 頂点 3 から頂点 2 への移動で赤い辺を 0 回、青い辺を 1 回
  • 頂点 2 から頂点 1 への移動で赤い辺を 1 回、青い辺を 0 回
  • 頂点 1 から頂点 4 への移動で赤い辺を 2 回、青い辺を 1 回

それぞれ通過し、全体では赤い辺を 3 回、青い辺を 3 回通るため、条件を満たします。

図

この他、1,3 番目の辺を青く、2 番目の辺を赤く塗るときも条件を満たし、これら以外の塗り方は条件を満たさないため、答えは 2 通りです。

入力例 2

3 10 10000
1 2 1 2 1 2 2 1 1 2
1 2
1 3

出力例 2

0

条件を満たす塗り方が存在しないこともあります。

入力例 3

10 2 -1
1 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

出力例 3

126

入力例 4

5 8 -1
1 4 1 4 2 1 3 5
1 2
4 1
3 1
1 5

出力例 4

2

Score : 500 points

Problem Statement

Given are a tree with N vertices, a sequence of M numbers A=(A_1,\ldots,A_M), and an integer K.
The vertices are numbered 1 through N, and the i-th edge connects Vertices U_i and V_i.

We will paint each of the N-1 edges of this tree red or blue. Among the 2^{N-1} such ways, find the number of ones that satisfies the following condition, modulo 998244353.

Condition:
Let us put a piece on Vertex A_1, and for each i=1,\ldots,M-1 in this order, move it from Vertex A_i to Vertex A_{i+1} along the edges in the shortest path. After all of these movements, R-B=K holds, where R and B are the numbers of times the piece traverses a red edge and a blue edge, respectively.

Constraints

  • 2 \leq N \leq 1000
  • 2 \leq M \leq 100
  • |K| \leq 10^5
  • 1 \leq A_i \leq N
  • 1\leq U_i,V_i\leq N
  • The given graph is a tree.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K
A_1 A_2 \ldots A_M
U_1 V_1
\vdots
U_{N-1} V_{N-1}

Output

Print the answer.

Sample Input 1

4 5 0
2 3 2 1 4
1 2
2 3
3 4

Sample Output 1

2

If we paint the 1-st and 3-rd edges red and the 2-nd edge blue, the piece will traverse the following numbers of red and blue edges:

  • 0 red edges and 1 blue edge when moving from Vertex 2 to 3,
  • 0 red edges and 1 blue edge when moving from Vertex 3 to 2,
  • 1 red edge and 0 blue edges when moving from Vertex 2 to 1,
  • 2 red edges and 1 blue edge when moving from Vertex 1 to 4,

for a total of 3 red edges and 3 blue edges, satisfying the condition.

Figure

Another way to satisfy the condition is to paint the 1-st and 3-rd edges blue and the 2-nd edge red. There is no other way to satisfy it, so the answer is 2.

Sample Input 2

3 10 10000
1 2 1 2 1 2 2 1 1 2
1 2
1 3

Sample Output 2

0

There may be no way to paint the tree to satisfy the condition.

Sample Input 3

10 2 -1
1 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

Sample Output 3

126

Sample Input 4

5 8 -1
1 4 1 4 2 1 3 5
1 2
4 1
3 1
1 5

Sample Output 4

2