2s/1G

题目描述

考虑一棵树，每个顶点上放置了一颗绿色或蓝色的石头。如果在执行以下操作 1 和 2 后能够满足条件 3，则称这样的树为“双子树”。

1. 首先，进行“选择由边直接连接的顶点对，并交换放置在每个端点上的石头”这一操作，可以进行零次或多次。
2. 其次，选择至多一条边并将其删除。
3. 此时，树被分割成至多两个连通分量，并且每个分量中只放置了一种颜色的石头。

你被给定一棵有 $N$ 个顶点且没有放置石头的树。在每个顶点上放置一颗石头共有 $2^N$ 种方式。其中有多少种方式满足以下条件？

• 选择一个叶子节点，并将其连同放置的石头一起移除。该操作之前和之后的树都必须是“双子树”。

因为答案可能很大，请输出答案除以 $998244353$ 的余数。

输入格式

$$\begin{aligned} & N \\ & u_1 \ v_1 \\ & \vdots \\ & u_{N-1} \ v_{N-1} \end{aligned}$$

输入满足以下约束：

• 所有输入均为整数。
• $2 \leq N \leq 10^5$
• $1 \leq u_i, v_i \leq N$
• 给定的图是一棵树。

输出格式

在一行中输出答案除以 $998244353$ 的余数。请在输出末尾添加换行符。

输入输出样例 #1

输入 #1

3
1 2
2 3

输出 #1

8

输入输出样例 #2

输入 #2

4
1 2
1 3
1 4

输出 #2

10

输入输出样例 #3

输入 #3

7
1 2
1 3
1 4
2 5
2 6
2 7

输出 #3

84

说明/提示

在样例输入 1 中，所有放置石头的方式都满足条件。

在样例输入 2 中，有 $10$ 种不同的放置方式使得初始状态是“双子树”。在移除一个叶子节点后，它们也仍然是“双子树”。

在样例输入 3 中，有 $86$ 种放置方式使得初始状态是“双子树”。其中有两种方式在移除任意一个叶子节点后不再是“双子树”。

翻译由 DeepSeek V3.2 完成