Random Forest Rank
Contest: Codeforces Round 518 (Div. 1) [Thanks, Mail.Ru!]
Difficulty rating: 2800
Tags: 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).

Input format:
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.

Output format:
Print one integer — answer to the problem.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
3
1 2
2 3

Example output:
6

Example input:
4
1 2
1 3
1 4

Example output:
14

Editorial:
I'll try to explain how to come up with this solution rather than just state the fact. For those who are more interested in getting AC, here is your fact: rank of a forest is twice the size of maximal matching.
When we see expected value, we usually want to somehow rewrite the thing under the expected value, apply linearity of expectation and then calculate some independent values. But that's not the case: rank behave strangely and we cannot rewrite it as sum of something, at least I don't know any such solutions (if you do, please write them in the comments). So it looks like we are forced to understand what rank is.
The rank of a matrix is a size of its largest non-vanishing minor. But our matrix is symmetric, maybe we can look only at symmetric minors (in a sense that we use the same set of rows and columns)? This is actually true but it is just a fact from linear algebra (seems to be not very well known) and has little to do with our problem, so I'll drop its proof and if someone is interested, ask me in comments.
Why do we like symmetric minors? Because they correspond to induced subgraphs of our graph. And all induced subgraphs of a forest are forests too! So let's study when a forest has full rank.
To do it, let's calculate determinant of its matrix. Matrix has full rank iff its determinant is non-zero. Let's write a determinant as a sum over all permutations.
$$$det A = \sum_{\pi} \prod_{i=1}^{n} A_{i \pi_{i}}$$$
If $$$A_{i \pi_{i}} \ne 0$$$ then we have edge $$$(i, \pi_{i})$$$ in our forest. Each permutation is a product of independent cycles. So to have non-zero product $$$\prod_{i=1}^{n} A_{i \pi_{i}}$$$ all the permutation cycles should be cycles in the forest. But forests have no cycles without repeating vertices! Well, actually they do: each edge generate one cycle of length $$$2$$$. And that's all, there are no other cycles in forest ($$$1$$$ vertex is not a cycle, because we don't have self-loops). To have non-zero product $$$\prod_{i=1}^{n} A_{i \pi_{i}}$$$ all cycles of permutation must have length $$$2$$$ and correspond to edges of forest. So we can divide all vertices in pairs, and in each pair there is an edge. That's the definition of perfect matching. Why can't they still result in zero sum? Because if there is a perfect matching in a forest then it is unique, so we actually have no more than one non-zero summand.
OK, forest has full rank is equivalent to forest has perfect matching. Suppose that $$$m$$$ is the size of maximal matching of a forest. Then no its induced subgraph of size strictly greater than $$$2m$$$ can have perfect matching. And there is a subgraph of size exactly $$$2m$$$ which does have perfect matching: the ends of edges in maximal matching.
Cool, we have proven the fact from the beginning. If you just want AC, continue reading from here. Now we have to calculate expected size of maximal matching. That sound much easier: we already have a linear DP which calculates maximal matching, and its values are exactly sizes of current maximal matching. To remind: $$$dp[v][taken]$$$ is a size of maximal matching in subtree rooted at $$$v$$$ where boolean flag $$$taken$$$ means did we already cover vertex $$$v$$$ or is it still free. All we have to do is to change the value stored in DP for expected value and also calculate probabilities to actually be in state with given flag $$$taken$$$.
Complexity — $$$O(n)$$$.