CF1067E Random Forest Rank

我们将无向图的秩定义为其邻接矩阵在 $ \mathbb{R}^{n \times n} $ 中的秩。 给定一棵树。树中的每条边都有 $1/2$ 的概率被删除，所有这些删除操作相互独立。设 $E$ 为最终得到的森林的期望秩。请计算 $E \cdot 2^{n-1}$ 模 $998244353$ 的值（可以证明 $E \cdot 2^{n-1}$ 是整数）。

第一行输入一个整数 $n$（$1 \le n \le 5 \cdot 10^{5}$），表示顶点数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u,\, v \le n;\, u \ne v$），表示一条连接顶点 $u$ 和 $v$ 的边。 保证给定的图是一棵树。

输出一个整数，表示题目的答案。

由 ChatGPT 4.1 翻译