E. Random Forest Rank
dp; graph matchings; math; trees
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.