E - 红色和蓝色的树

得分: $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$ 放置一个棋子，在每次移动之前，沿最短路径从顶点 $A_i$ 移动到顶点 $A_{i+1}$。在所有的移动结束后，满足 $R-B=K$ 的染色方案的数量，其中 $R$ 和 $B$ 分别是棋子经过红色边和蓝色边的次数。

约束

• $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}$

输出

输出答案。

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