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