Random Forest Rank

题意翻译

给定一棵$n$个节点的树 ，每条边有$\frac{1}{2}$的概率出现，可以得到一个森林,求这个森林邻接矩阵的秩的期望。

题目描述

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).

输入输出格式

输入格式

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.

输出格式

Print one integer — answer to the problem.

输入输出样例

输入样例 #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