红蓝树

题目描述

给定一棵有 $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}$

输出格式

输出答案。

样例

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

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$。

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 \le N \le 1000$
• $2 \le M \le 100$
• $|K| \le 10^5$
• $1 \le A_i \le N$
• $1 \le U_i, V_i \le N$
• 给定的图是一棵树。
• 输入中的所有值均为整数。