分数: 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