← 返回题目列表

AtCoder · arc121_f

F. 树上的逻辑运算

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

分数: 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} is OR,将新顶点标记为 \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.