← 返回题目列表

Codeforces · 1067/E

E. 随机森林排名

中文机器翻译题面 查看原题

让我们将无向图的秩定义为其邻接矩阵在 $$$\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$$$) — 由边连接的顶点的索引。

保证给定的图是一棵树。

输出

打印一个整数——问题的答案。

示例

输入 #1

3
1 2
2 3

输出 #1

6

输入 #2

4
1 2
1 3
1 4

输出 #2

14

输入 #3

4
1 2
2 3
3 4

输出 #3

18