Type: Default 1000ms 256MiB

Red and Blue Tree

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC222E] Red and Blue Tree

题目描述

给出 NN 个点的树和长度为 MM 的序列 aa。现需要给每条边染成红色(red)或者蓝色(blue),要求按照 aa 走的路径,经过的边数满足: 红色 − 蓝色 = KK,问方案数。对 998244353998244353 取模。

输入格式

第一行三个整数 N,M,KN,M,K ,第二行 MM 个整数表示序列 aa ,接下来 N1N-1 行每行两个整数表示树的一条边。

N N M M K K A1 A_1 A2 A_2 \ldots AM A_M U1 U_1 V1 V_1 \vdots UN1 U_{N-1} VN1 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  N  10002\ \leq\ N\ \leq\ 1000
  • 2  M  1002\ \leq\ M\ \leq\ 100
  • K  105|K|\ \leq\ 10^5
  • 1  Ai  N1\ \leq\ A_i\ \leq\ N
  • 1 Ui,Vi N1\leq\ U_i,V_i\leq\ N
  • 序列 aa 中的相邻两个元素不一定是树边

样例解释 1

根据序列 aa ,路径经过了三次边 (2,3)(2,3) ,两次边 (1,2)(1,2) ,一次边 (3,4)(3,4) 。因此只需要边 (1,2)(1,2) 和边 (3,4)(3,4) 同色,边 (2,3)(2,3) 是另一种颜色即可,共有 22 种方案。

20250304集训

Not Attended
Status
Done
Rule
IOI
Problem
8
Start at
2025-3-4 19:00
End at
2025-3-4 21:12
Duration
2.2 hour(s)
Host
Partic.
12