← 返回题目列表

Codeforces · 1032/F

F. Vasya 和最大匹配

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

Vasya 有一棵由 $$$n$$$ 个顶点组成的树。他想删除这棵树中的一些(可能是零)边,以便结果图中的最大匹配是唯一的。他要求你计算选择一组要删除的边的方法数。

图中的匹配是其边的子集,使得子集中的两条(或更多)边没有关联的顶点。最大匹配是使得子集中的边的数量在该图中的所有匹配中是最大可能的匹配。

由于答案可能很大,因此输出它对 $$$998244353$$$ 取模。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 树中的顶点数。

接下来的 $$$n − 1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$) 表示顶点 $$$u$$$ 和顶点 $$$v$$$ 之间的边。保证这些边形成一棵树。

输出

打印一个整数 — 删除某些(可能为空)边子集的方法数,以便结果图中的最大匹配是唯一的。打印答案对 $$$998244353$$$ 取模。

示例

输入 #1

4
1 2
1 3
1 4

输出 #1

4

输入 #2

4
1 2
2 3
3 4

输出 #2

6

输入 #3

1

输出 #3

1

注意

在第一个示例中删除边的可能方法:

- 删除 $$$(1, 2)$$$ 和 $$$(1, 3)$$$。
- 删除 $$$(1, 2)$$$ 和 $$$(1, 4)$$$。
- 删除 $$$(1, 3)$$$ 和 $$$(1, 4)$$$。
- 删除所有边。

在第二个示例中删除边的可能方法:

- 不删除任何边。
- 删除 $$$(1, 2)$$$ 和 $$$(2, 3)$$$。
- 删除 $$$(1, 2)$$$ 和 $$$(3, 4)$$$。
- 删除 $$$(2, 3)$$$ 和 $$$(3, 4)$$$。
- 删除 $$$(2, 3)$$$。
- 删除所有边。