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=K$，其中 $R$ 和 $B$ 分别是棋子经过的红色边和蓝色边的次数。

输入格式

输入按照标准输入给出，格式如下： $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

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 \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$ 条和第 $3$ 条边涂成红色，第 $2$ 条边涂成蓝色，棋子将经过如下数量的红色和蓝色边：

从顶点 $2$ 到 $3$ 时经过 $0$ 条红边和 $1$ 条蓝边， 从顶点 $3$ 到 $2$ 时经过 $0$ 条红边和 $1$ 条蓝边， 从顶点 $2$ 到 $1$ 时经过 $1$ 条红边和 $0$ 条蓝边， 从顶点 $1$ 到 $4$ 时经过 $2$ 条红边和 $1$ 条蓝边，

总计 $3$ 条红边和 $3$ 条蓝边，满足条件。 另一种满足条件的方法是把第 $1$ 条和第 $3$ 条边涂成蓝色，第 $2$ 条边涂成红色。没有其他方法满足条件，所以答案为 $2$.
也有可能不存在任何涂色方法满足该条件。

标签: AtCoder|abc222E

来源

AtCoder|abc222E