F - Preserve Diameter Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

1 から N までの番号がつけられた N 個の頂点を持つ木 G があります。 G の i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

G に 0 本以上の辺を追加することを考えます。 追加後のグラフを H とします。

以下の 4 つの条件を満たす H の個数を 998244353 で割ったあまりを求めてください。

  • H に多重辺は存在しない
  • H に自己ループは存在しない
  • G の直径と H の直径は等しい
  • H に辺が存在しない任意の頂点対について、H にその頂点対間を結ぶ辺を追加すると、直径が短くなる

制約

  • 3 \le N \le 2 \times 10^5
  • 1 \le a_i, b_i \le N
  • 入力で与えられるグラフは木

入力

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

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

出力

答えを出力せよ。

入力例 1

6
1 6
2 1
5 2
3 4
2 3

出力例 1

3

例えば、G に辺 (1, 5), (3, 5) を追加したグラフは問題文中の 4 つの条件を満たします。

入力例 2

3
1 2
2 3

出力例 2

1

H として考えられるグラフは、G のみです。

入力例 3

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

出力例 3

27

入力例 4

19
2 4
15 8
1 16
1 3
12 19
1 18
7 11
11 15
12 9
1 6
7 14
18 2
13 12
13 5
16 13
7 1
11 10
7 17

出力例 4

78732

Score : 1100 points

Problem Statement

We have a tree G with N vertices numbered 1 to N. The i-th edge of G connects Vertex a_i and Vertex b_i.

Consider adding zero or more edges in G, and let H be the graph resulted.

Find the number of graphs H that satisfy the following conditions, modulo 998244353.

  • H does not contain self-loops or multiple edges.
  • The diameters of G and H are equal.
  • For every pair of vertices in H that is not directly connected by an edge, the addition of an edge directly connecting them would reduce the diameter of the graph.

Constraints

  • 3 \le N \le 2 \times 10^5
  • 1 \le a_i, b_i \le N
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

Output

Print the answer.

Sample Input 1

6
1 6
2 1
5 2
3 4
2 3

Sample Output 1

3

For example, adding the edges (1, 5), (3, 5) in G satisfies the conditions.

Sample Input 2

3
1 2
2 3

Sample Output 2

1

The only graph H that satisfies the conditions is G.

Sample Input 3

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

Sample Output 3

27

Sample Input 4

19
2 4
15 8
1 16
1 3
12 19
1 18
7 11
11 15
12 9
1 6
7 14
18 2
13 12
13 5
16 13
7 1
11 10
7 17

Sample Output 4

78732