题目描述

给定一棵有 $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$ 取模的结果。

样例 1

输入

2
1 2

输出

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

输出

283374562

说明/提示

注释

• 运算 $\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 翻译