← 返回题目列表

AtCoder · agc052_f

F. 树顶点异或

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

分数: 2000 点

问题陈述

你得到了一棵树 N 顶点。 顶点编号从 1 to N,以及 i第一条边连接顶点 u_i 和 v_i.

最初,在树的每个顶点上写有数字 1.

在一次操作中,您可以执行以下操作:

  • 选择任意顶点 树的 v 。让 X 是 异或 写入邻居的值 v。那么,如果上面写的数字 v is a_v,替换为 (a_v\ \mathrm{XOR}\ X).

您可以执行此操作任意有限次(可能为零)。您可以实现多少种配置?由于这个数字可能很大,因此输出它的模 998244353.

如果存在顶点,则两个配置被称为不同 v,这样写的数字 v 这些配置是不同的。

约束

  • 3 \le N \le 2\cdot 10^5
  • 1\le u_i, v_i \le N
  • u_i \neq v_i
  • 输入代表一棵有效的树。

输入

输入由标准输入按以下格式给出:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

输出

输出从初始状态可以得到的配置数量,模 998244353.


示例输入 1

4
1 2
2 3
3 4

示例输出 1

10

我们可以获得以下配置(abcd 表示顶点 1,2,3,4 有 a,b,c,d 写在上面): 1111, 1110, 1100, 1000, 0111, 0110, 0100, 0011, 0010, 0001.


示例输入 2

5
1 2
1 3
1 4
1 5

示例输出 2

24

示例输入 3

6
1 3
2 3
3 4
4 5
4 6

示例输出 3

40

示例输入 4

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

示例输出 4

255