分数: 500 点
问题陈述
给定一棵树 N 顶点,一系列 M 号码 A=(A_1,\ldots,A_M),和一个整数 K.
顶点已编号 1 通过 N,以及 i第一条边连接顶点 U_i 和 V_i.
我们将绘制每个 N-1 这棵树的边缘为红色或蓝色。其中 2^{N-1} 这样,找到满足以下条件的个数,取模 998244353.
条件:
让我们在 Vertex 上放一块 A_1,并且对于每个 i=1,\ldots,M-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}
输出
打印答案。
样本输入 1
4 5 0 2 3 2 1 4 1 2 2 3 3 4
示例输出 1
2
如果我们画 1-st 和 3-rd 边缘为红色且 2-nd 蓝色边,该棋子将穿过以下数量的红色和蓝色边:
- 0 红色边缘和 1 从顶点移动时的蓝色边缘 2 to 3,
- 0 红色边缘和 1 从顶点移动时的蓝色边缘 3 to 2,
- 1 红边和 0 从顶点移动时出现蓝色边缘 2 to 1,
- 2 红色边缘和 1 从顶点移动时的蓝色边缘 1 to 4,
总共 3 红色边缘和 3 蓝色边缘,满足条件。

满足条件的另一种方法是绘制 1-st 和 3-rd 边缘为蓝色, 2-nd 边缘红色。没有其他办法可以满足,所以答案是 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