← Home
write a go solution for Description:
Let's define rank of undirected graph as rank of its adjacency matrix in mathbbR^nxn.

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*2^n-1 modulo 998244353 (it is easy to show that E*2^n-1 is an integer).

Input Format:
First line of input contains n (1<=n<=5*10^5) — number of vertices.

Next n-1 lines contains two integers u v (1<=u,,,v<=n;,,unev) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.

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

Note:
None. Output only the code with no comments, explanation, or additional text.