409716: GYM103698 F Tree

Long time ago, there was a lamb who had a tree of $$$n$$$ vertices, indexed from $$$1$$$ to $$$n$$$, and the lamb liked it very much.

However, on a night of lightning and thunder, a Peng flew into the sky and summoned lightning which cut off several edges of the tree.

The angry lamb wanted to know the sum of the indices of the vertices that are the centroids of each connected component. If there were two centroids in one connected component, both of them would be considered by the sum. Because the lamb didn't know which edges are cut off, it wanted to know the sum of "the sum of the indices" for all $$$2^{n-1}$$$ possible cases.

On a tree of $$$n$$$ vertices, a vertex is a centroid if and only if after removing it from the tree, each connected component in the result includes at most $$$n/2$$$ vertices. It can be proven that each tree has at most two different centroids.

Because the answer can be extremely large, you just need to tell the answer modulo $$$998244353$$$.

The first line contains one integer $$$n$$$, representing the number of vertices in the tree.

For the following $$$n-1$$$ lines, each line contains two positive integers $$$u_i, v_i$$$, representing an edge $$$(u_i, v_i)$$$ on the tree.

One integer, representing the answer modulo $$$998244353$$$.

3
1 2
2 3

20

5
1 2
1 3
2 4
2 5

168

Subtask 1 (10pts): $$$n \le 15$$$.

Subtask 2 (30pts): $$$n \le 300$$$.

Subtask 3 (15pts): $$$n \le 1000$$$.

Subtask 4 (5pts): The $$$i$$$ edge satisfies $$$u_i=i,v_i=i+1$$$.

Subtask 5 (40pts): No special properties.

For $$$100\%$$$ of data, $$$n\leq 3000$$$ is guaranteed.