A - Meeting on Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

頂点に 1,2,\dots, N の番号がついた N 頂点の木が与えられます. i=1,2,\dots, N-1 について，i 番目の辺は頂点 u_i,v_i を結んでいます.

木の各頂点には 1 匹ずつリスがいます. リスたちは次のようにして会議を開こうとしています.

  1. 会議に参加するリスを 1 匹以上選ぶ.
  2. 選ばれたリスたちは相談し，木の頂点をひとつ選んで会議の開催地とする.
  3. 選ばれたリスたちはそれぞれ，会議の開催地に到達するまで，木の辺を辿って移動する.

リスの移動には辿った辺の個数に等しいコストがかかります. そこで，会議のコストを，選ばれたリスの移動にかかるコストの総和として定めます. リスたちは会議の開催地をうまく選ぶことで，会議のコストをできるだけ小さくしたいと考えています.

会議に参加するリスを 1 匹以上選ぶ方法は 2^N-1 通りありますが，そのそれぞれに対する「会議の開催地を適切に選んだときの会議のコストの最小値」の総和を 998244353 で割ったあまりを求めてください.

制約

  • 2\le N\le 3\times 10^5
  • 1\le u_i,v_i\le N
  • 与えられるグラフは木をなす
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる.

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

答えを出力せよ.

入力例 1

4
1 2
1 3
1 4

出力例 1

21

たとえば，頂点 1,2,3 にいるリスが会議に参加する場合，頂点 1 を開催地に選ぶのが適切で，このときのコストは 2 です.

2^4-1=15 通りのリスの選び方に対する「会議の開催地を適切に選んだときの会議のコストの最小値」の総和は 21 です.

入力例 2

5
1 2
2 3
3 4
3 5

出力例 2

70

入力例 3

12
1 2
1 3
3 4
4 5
3 6
6 7
6 8
1 9
9 10
10 11
9 12

出力例 3

43813

Score : 600 points

Problem Statement

You are given a tree with N vertices numbered 1,2,\dots, N. For i=1,2,\dots, N-1, the i-th edge connects vertices u_i and v_i.

There is one squirrel at each vertex of the tree. The squirrels are trying to hold a meeting as follows.

  1. Choose one or more squirrels to participate in the meeting.

  2. The chosen squirrels consult with each other and choose one vertex of the tree as the venue for the meeting.

  3. Each of the chosen squirrels moves along the edges of the tree until it reaches the venue.

A squirrel's movement incurs a cost equal to the number of edges it traverses. We define the cost of the meeting as the sum of the movement costs of the chosen squirrels. The squirrels want to choose the venue of the meeting so that the cost of the meeting is minimized.

There are 2^N-1 ways to choose one or more squirrels to participate in the meeting. Find the sum, modulo 998244353, over all of these ways, of the minimum cost of the meeting when the venue is chosen appropriately.

Constraints

  • 2\le N\le 3\times 10^5
  • 1\le u_i,v_i\le N
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Output the answer.

Sample Input 1

4
1 2
1 3
1 4

Sample Output 1

21

For example, if the squirrels at vertices 1,2,3 participate in the meeting, it is appropriate to choose vertex 1 as the venue, and the cost in this case is 2.

The sum, over all 2^4-1=15 ways of choosing the squirrels, of the minimum cost of the meeting when the venue is chosen appropriately is 21.

Sample Input 2

5
1 2
2 3
3 4
3 5

Sample Output 2

70

Sample Input 3

12
1 2
1 3
3 4
4 5
3 6
6 7
6 8
1 9
9 10
10 11
9 12

Sample Output 3

43813