AT_agc052_f.[AGC052F] Tree Vertices XOR

有一棵包含 $N$ 个顶点的树，顶点编号为从 $1$ 到 $N$。每条边将两个顶点相连，其中第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

最开始，所有顶点上都写着数字 $1$。

你可以进行以下操作任意次（也可以一次都不进行）：

• 从树中选择一个顶点 $v$。将与 $v$ 相邻的所有顶点上的数值做 XOR 运算，得到结果 $X$。然后，将顶点 $v$ 上的数值 $a_v$ 替换为 $(a_v\ \mathrm{XOR}\ X)$。

你需要计算通过这些操作可以得到多少种不同的树形态。由于结果可能非常大，请输出它对 $998244353$ 取模的值。

在这里，两个树形态被认为不同，如果存在至少一个顶点 $v$ 使得这两个形态在该顶点上的数字不同。

输入依次包括：

$ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \cdots $ $ u_{N-1} $ $ v_{N-1} $

输出表示可以达到的不同树形态数量对 $998244353$ 取模的结果。

• $ 3 \le N \le 2 \cdot 10^5 $
• $ 1 \le u_i, v_i \le N $
• $ u_i \neq v_i $
• 输入表示的图是一棵树。

样例解释 1

假设在顶点 $1, 2, 3, 4$ 上分别写着 $a, b, c, d$。可能的不同形态包括 $1111$、$1110$、$1100$、$1000$、$0111$、$0110$、$0100$、$0011$、$0010$、$0001$。

本翻译由 AI 自动生成