题目描述

$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$ である。

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

给出$n$个点的树和长度为$m$的序列$a$。现需要给每条边染成红色(red)或者蓝色(blue)，要求按照$a$走的路径，经过的边数$红色−蓝色=k$，问方案数。

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

2

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

0

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

126

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

2

提示

制約

• $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$
• 与えられるグラフは木である
• 入力に含まれる値は全て整数である

Sample Explanation 1

$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$ 通りです。

Sample Explanation 2

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