分数: 800 点
问题陈述
给定一棵树 N 顶点编号 1 通过 N.
的 树的 i第一条边连接顶点 a_i 和 b_i.
Snuke 将用以下标签标记每个顶点 0 or 1 和每条边 AND or OR。
其中 2^{2N-1} 标记顶点和边的方法,找到满足以下条件的方法的数量,取模 998244353.
条件:存在一系列 N-1 操作以一个顶点标记结束 1,其中每个操作都包含以下步骤。
- 选择一条边并将其收缩。在这里,让 x 和 y 是已擦除顶点的标签, \mathrm{op} 是擦除边缘的标签。
- If \mathrm{op} is
AND,将新顶点标记为 \mathrm{AND}(x,y);如果 \mathrm{op} isOR,将新顶点标记为 \mathrm{OR}(x,y).
注释
- 操作 \mathrm{AND} 定义如下: \mathrm{AND}(0,0)=(0,1)=(1,0)=0,\mathrm{AND}(1,1)=1.
- 操作 \mathrm{OR} 定义如下: \mathrm{OR}(1,1)=(0,1)=(1,0)=1,\mathrm{OR}(0,0)=0.
- 收缩连接顶点的边时 s 和顶点 t,我们合并两个顶点,同时删除该边。收缩后,有一条边连接新顶点和顶点 u 当且仅当有一条边连接 s 和 u 或正在连接 t 和 u 收缩前。
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 10^{5}
- 1 \leq a_i, b_i \leq N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
输出
打印满足问题陈述中条件的标记树的方法数,模数 998244353.
示例输入 1
2 1 2
示例输出 1
4
示例输入 2
20 7 3 20 18 16 12 7 2 10 5 18 16 16 3 4 11 7 15 8 1 6 1 12 13 15 5 19 17 7 1 9 8 7 17 16 14 11 7
示例输出 2
283374562
- 记住打印计数模数 998244353.