← 返回题目列表

AtCoder · abc222_e

H. 红蓝树

中文机器翻译题面 查看原题

分数: 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 蓝色边缘,满足条件。

Figure

满足条件的另一种方法是绘制 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