AT_arc121_f [ARC121F] Logical Operations on Tree

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。 第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。 すぬけ君打算给每个顶点标记 `0` 或 `1`，给每条边标记 `AND` 或 `OR`。顶点和边的所有标记方法共有 $2^{2N-1}$ 种。在这些标记方法中，满足以下条件的方法数对 $998244353$ 取模是多少？ 条件：存在一种操作顺序，使得经过 $N-1$ 次操作后，剩下的顶点的标记为 `1`。操作如下： - 选择一条边进行缩约（设被合并的两个顶点的标记为 $x, y$，被合并的边的标记为 $\mathrm{op}$）。 - 如果 $\mathrm{op}$ 是 `AND`，则新顶点的标记为 $\mathrm{AND}(x, y)$；如果是 `OR`，则新顶点的标记为 $\mathrm{OR}(x, y)$。

输入按以下格式从标准输入给出。 > $N$ > $a_1$ $b_1$ > $\vdots$ > $a_{N-1}$ $b_{N-1}$

输出满足题目条件的标记方法数对 $998244353$ 取模的结果。

### 注释 - 运算 $\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$ 的边时，除了移除该边，还要将 $s$ 和 $t$ 合并。合并后，若缩约前 $s$ 与 $u$ 或 $t$ 与 $u$ 有边，则缩约后新顶点与 $u$ 有边，且仅在这种情况下有边。 ### 数据范围 - 所有输入均为整数。 - $2 \leq N \leq 10^5$ - $1 \leq a_i, b_i \leq N$ - 输入保证是一棵树。 ### 样例解释 2 - 不要忘记对 $998244353$ 取模输出。 由 ChatGPT 4.1 翻译