C - Equal Degree Deletion 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 900 点

問題文

N 頂点 N-1 辺からなる木 G が与えられます。
頂点には 1 から N までの、辺には 1 から N-1 までの番号が付いており、辺 i は頂点 u_i と v_i を結んでいます。

木 H に対して以下の操作を 0 回以上行って H に含まれる辺をすべて削除することができるとき、H を特別であると呼ぶことにします。

  • その時点で次数が等しいような 2 頂点を結ぶ辺を選んでそれを削除する。

G の部分木のうち特別であるようなものの総数を 998244353 で割った余りを求めてください。

1 つの入力につき、T 個のテストケースを解いてください。

部分木とは 木 G の部分木とは、G の連結な部分グラフのことを指します。

制約

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 3 \times 10^5
  • すべてのテストケースにおける N の総和は 3 \times 10^5 以下
  • 1 \leq u_i \lt v_i \leq N
  • 与えられるグラフ G は木である
  • 入力される値はすべて整数

入力

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

T  
\mathrm{case}_1  
\mathrm{case}_2  
\vdots  
\mathrm{case}_T

各テストケース \mathrm{case}_t は以下の形式で与えられる。

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

出力

答えを合計 T 行で出力せよ。 t 行目には、t 番目のテストケースの答えを出力せよ。

入力例 1

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

出力例 1

15
35
3

1 つ目のテストケースでは、1 頂点からなる部分木 6 個、2 頂点と 1 辺からなる部分木 5 個は特別です。 また、頂点 1,3,4,6 と辺 1,3,5 からなる G の部分木に対して辺 3,5,1 の順に辺を削除する操作を行えるため、この木も特別です。

Score : 900 points

Problem Statement

You are given a tree G with N vertices and N-1 edges.
The vertices are numbered 1 to N, and the edges are numbered 1 to N-1. Edge i connects vertices u_i and v_i.

A tree H is called special if it is possible to delete all edges of H by performing the following operation zero or more times.

  • Choose an edge connecting two vertices whose current degrees are equal, and delete it.

Find the number of special subtrees of G, modulo 998244353.

Solve T test cases for each input.

What is a subtree? A subtree of a tree G is a connected subgraph of G.

Constraints

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 3 \times 10^5
  • The sum of N over all test cases is at most 3 \times 10^5.
  • 1 \leq u_i \lt v_i \leq N
  • The given graph G is a tree.
  • All input values are integers.

Input

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

T  
\mathrm{case}_1  
\mathrm{case}_2  
\vdots  
\mathrm{case}_T

Each test case \mathrm{case}_t is given in the following format:

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

Output

Print T lines in total. The t-th line should contain the answer for the t-th test case.

Sample Input 1

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

Sample Output 1

15
35
3

In the first test case, the 6 subtrees consisting of one vertex and the 5 subtrees consisting of two vertices and one edge are special. Also, the subtree of G consisting of vertices 1,3,4,6 and edges 1,3,5 is special, since the operation can be performed to delete edges 3,5,1 in this order.