Independent Set (Sum)

Time limit1sMemory limit2048 MB

Summary

Given a tree, sum over all non-empty independent node sets the set size times the edges needed to connect it, modulo 998244353.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

You are given a tree with $N$ nodes, numbered from $1$ to $N$ . The edges are numbered from $1$ to $N - 1$ , and edge $i$ connects nodes $U_i$ and $V_i$ .

A non-empty set of nodes is independent if no two nodes in the set are adjacent. The red nodes in the first figure are members of the set.

The score of an independent set is the number of nodes in the set multiplied by the minimum number of edges needed to keep all nodes in the set connected. The second figure shows a set with $2$ nodes whose minimum connecting edge count is $3$ , so its score is $2 \cdot 3 = 6$ . The score of a set with only one node is $0$ .

Find the sum of the scores over all non-empty independent sets in the tree. The result can be very large, so print it modulo $998244353$ .

Input

The first line contains an integer $N$ ( $2 \le N \le 100000$ ).

Each of the next $N - 1$ lines contains two integers $U_i$ and $V_i$ ( $1 \le U_i, V_i \le N$ ). The given edges form a tree.

Output

Print one integer, the sum of the scores over all non-empty independent sets, modulo $998244353$ .

Examples2

Example 1
Input
```
5
1 2
1 3
3 4
3 5
```
Expected output
```
49
```
Example 2
Input
```
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
```
Expected output
```
616
```