C - Shrink the Tree Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1500 点

問題文

1 から N までの番号のついた N 頂点からなる木 T が与えられます． i 番目の辺は頂点 A_i と B_i を結んでいます．

あなたは以下の操作を好きな回数 (0 回でもよい) 行うことができます．

  • T の 2 つの葉 u,v であって，その距離が奇数であるものを選ぶ． そして，u,v を(それらに接続する辺とともに) T から削除する．

ここで，ある頂点が葉であるとは，操作を行おうとする時点でその次数がちょうど 1 であることを意味します． また，2 つの頂点の距離とは，その頂点間を結ぶパスに含まれる辺の個数です．

操作後の T に含まれる頂点集合としてありうるものが何通りあるかを 998244353 で割ったあまりを求めてください．

制約

  • 2 \leq N \leq 150
  • 1 \leq A_i,B_i \leq N
  • 入力で与えられるグラフは木である．
  • 入力される値はすべて整数．

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

答えを出力せよ．

入力例 1

4
1 2
2 3
3 4

出力例 1

3

1 度も操作を行わないことで，頂点集合 \{1,2,3,4\} を得ることができます．

T の葉 1,4 を消すことで，頂点集合 \{2,3\} を得ることができます．

ここから更に葉 2,3 を消すことで，頂点集合 \{\} を得ることができます．

入力例 2

5
2 1
3 1
4 1
5 3

出力例 2

3

入力例 3

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

出力例 3

11

入力例 4

24
12 7
14 4
8 13
24 13
1 3
4 9
17 2
1 21
24 22
11 1
15 17
22 5
23 10
24 12
13 6
12 16
10 21
19 22
20 17
4 20
20 6
10 18
21 6

出力例 4

5359

Score : 1500 points

Problem Statement

You are given a tree T with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.

You can perform the following operation any number of times, possibly zero.

  • Choose two leaves u and v of T such that the distance between them is odd. Then, remove u and v from T (along with the incident edges).

Here, a vertex is said to be a leaf when its degree is exactly one at the time of the operation. The distance between two vertices is the number of edges in the path connecting those vertices.

Find the number, modulo 998244353, of sets that can be the vertex set of T after your operations.

Constraints

  • 2 \leq N \leq 150
  • 1 \leq A_i,B_i \leq N
  • The input graph is a tree.
  • All input values are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Print the answer.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

3

Performing zero operations yields the vertex set \{1,2,3,4\}.

Erasing the leaves 1 and 4 from T yields the vertex set \{2,3\}.

From this state, erasing the leaves 2 and 3 yields the vertex set \{\}.

Sample Input 2

5
2 1
3 1
4 1
5 3

Sample Output 2

3

Sample Input 3

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

Sample Output 3

11

Sample Input 4

24
12 7
14 4
8 13
24 13
1 3
4 9
17 2
1 21
24 22
11 1
15 17
22 5
23 10
24 12
13 6
12 16
10 21
19 22
20 17
4 20
20 6
10 18
21 6

Sample Output 4

5359