AT_abc222_e [ABC222E] Red and Blue Tree

题目描述

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

输出格式

输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

0

输入输出样例 #3

输入 #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

输入 #4

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

输出 #4

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$
• 给定的图一定是一棵树
• 输入中的所有值均为整数

样例解释 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$。

样例解释 2

也有可能不存在满足条件的涂色方法。

由 ChatGPT 4.1 翻译