CF1067E.Random Forest Rank

Let's define rank of undirected graph as rank of its adjacency matrix in $\mathbb{R}^{n \times n}$.

Given a tree. Each edge of this tree will be deleted with probability $1/2$, all these deletions are independent. Let $E$ be the expected rank of resulting forest. Find $E \cdot 2^{n-1}$ modulo $998244353$ (it is easy to show that $E \cdot 2^{n-1}$ is an integer).

我们定义无向图的秩为其邻接矩阵在 $\mathbb{R}^{n \times n}$ 中的秩。

给定一棵树。该树的每条边以概率 $1/2$ 被删除，且所有删除操作相互独立。设 $E$ 为所得森林的秩的期望值。求 $E \cdot 2^{n-1}$ 对 $998244353$ 取模的值（容易证明 $E \cdot 2^{n-1}$ 是整数）。

First line of input contains $n$ ($1 \le n \le 5 \cdot 10^{5}$) — number of vertices.

Next $n-1$ lines contains two integers $u$ $v$ ($1 \le u, \,\, v \le n; \,\, u \ne v$) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.

输入的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^{5}$）—— 表示顶点的数量。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, \,\, v \le n; \,\, u \ne v$）—— 表示由一条边连接的两个顶点的编号。

保证给定的图是一棵树。

Print one integer — answer to the problem.

输出一个整数——问题的答案。