← 返回题目列表

Codeforces · 1799/H

H. 砍树

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

给你一棵有 $$$n$$$ 个顶点的树。

英雄 $$$k$$$ 次执行以下操作:

- 选择一些边。
- 删除它。
- 取出剩下的两个部分之一并将其删除。
- 在剩余部分写入顶点数。

您将获得一棵初始树和一系列书面数字。找出使所写数字等于给定数字的运算方法的数量。由于答案可能很大,请通过对$$$998\,244\,353$$$求模来找到它。如果在某些操作边缘或剩余部分选择不同,则两种方式被认为是不同的。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5000$$$) — 顶点数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$s$$$, $$$f$$$ ($$$1 \leq s, f \leq n$$$, $$$s \neq f$$$) — 边 $$$(s, f)$$$ 的描述。

下一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq \min{(6, n - 1)}$$$) — 操作数。

下一行包含 $$$k$$$ 整数 $$$s_1, s_2, \ldots, s_k$$$ ($$$n > s_1 > s_2 > \ldots > s_k \geq 1$$$) — 书面数字。

输出

打印一个整数 — 问题的答案以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3
1 2
2 3
2
2 1

输出 #1

4

输入 #2

7
2 1
3 2
4 1
5 3
6 4
7 4
2
4 2

输出 #2

2

输入 #3

7
1 2
1 3
1 4
2 5
3 6
4 7
1
2

输出 #3

3

输入#4

7
1 2
1 3
1 4
2 5
3 6
4 7
4
6 5 2 1

输出#4

24

输入 #5

8
1 2
2 3
3 4
3 5
3 6
3 7
3 8
2
7 4

输出 #5

0

注意

在第一个测试中,有四种可能的操作方式:

- 删除边 $$$(1, 2)$$$ 并删除顶点 $$$1$$$。删除边 $$$(2, 3)$$$ 并删除顶点 $$$2$$$。
- 删除边 $$$(1, 2)$$$ 并删除顶点 $$$1$$$。删除边 $$$(3, 2)$$$ 并删除顶点 $$$3$$$。
- 删除边 $$$(3, 2)$$$ 并删除顶点 $$$3$$$。删除边 $$$(1, 2)$$$ 并删除顶点 $$$1$$$。
- 删除边 $$$(3, 2)$$$ 并删除顶点 $$$3$$$。删除边 $$$(2, 1)$$$ 并删除顶点 $$$2$$$。

在第二个测试中,有两种可能的操作方式:

- 删除边 $$$(4, 1)$$$ 并删除带有顶点 $$$4$$$ 的部分。删除边 $$$(2, 3)$$$ 并删除带有顶点 $$$2$$$ 的部分。
- 删除边 $$$(4, 1)$$$ 并删除带有顶点 $$$4$$$ 的部分。删除边 $$$(3, 2)$$$ 并删除带有顶点 $$$3$$$ 的部分。