P15710 [JAG 2023 Summer Camp #2] Gemini Tree (Ver.Lapislazuli)

考虑一棵树，每个顶点上放置了一颗绿色或蓝色的石头。如果在执行以下操作 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 中，所有放置石头的方式都满足条件。 在样例输入 2 中，有 $10$ 种不同的放置方式使得初始状态是“双子树”。在移除一个叶子节点后，它们也仍然是“双子树”。 在样例输入 3 中，有 $86$ 种放置方式使得初始状态是“双子树”。其中有两种方式在移除任意一个叶子节点后不再是“双子树”。 翻译由 DeepSeek V3.2 完成