/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点からなる木が与えられます。 頂点は 1 , 2 , \ldots , N と番号付けられており、 1\leq i\leq N-1 について、i 本目の辺は頂点 U_i と頂点 V_i を結んでいます。 木の直径を D とするとき、木の頂点のうち 2 点以上を選んで赤く塗る方法であって、 赤く塗られたどの頂点の間の距離も D であるようなものの数を 998244353 で割った余りを求めてください。
ただし、木の 2 頂点の間の距離は一方から他方へ移動するときに用いる辺の本数の最小値であり、 木の直径は任意の 2 頂点の間の距離の最大値として定められます。
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq U_i,V_i \leq N
- U_i \neq V_i
- 入力は全て整数である。
- 与えられるグラフは木である。
入力
入力は以下の形式で標準入力から与えられる。
N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
出力
答えを出力せよ。
入力例 1
5 1 2 1 3 1 4 4 5
出力例 1
2
与えられた木は 5 頂点からなり、直径は 3 です。
2 頂点の組であって、その間の距離が 3 であるようなものは (2,5) , (3,5) しか存在しないため、
条件をみたす塗り方は \lbrace 2,5\rbrace と \lbrace 3,5\rbrace の 2 通りとなります。
\lbrace 2,3,5\rbrace は頂点 2 と頂点 3 の間の距離が 2 であるため条件をみたさないことに注意してください。
入力例 2
4 1 2 1 3 1 4
出力例 2
4
直径は 2 であり、条件をみたす塗り方は \lbrace 2,3\rbrace , \lbrace 2,4\rbrace , \lbrace 3,4\rbrace , \lbrace 2,3,4\rbrace の 4 通りとなります。
Score : 500 points
Problem Statement
Given is a tree with N vertices. The vertices are numbered 1, 2, \ldots, N, and for each 1\leq i\leq N-1, the i-th edge connects Vertex U_i and Vertex V_i. Let D be the diameter of the tree. Find the number, modulo 998244353, of ways to choose two or more of the vertices and paint them red so that all distances between two red vertices are D.
Here, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of the tree is the maximum distance between two vertices.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1 \leq U_i,V_i \leq N
- U_i \neq V_i
- All values in input are integers.
- The given graph is a tree.
Input
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
Print the answer.
Sample Input 1
5 1 2 1 3 1 4 4 5
Sample Output 1
2
The given tree has five vertices and a diameter of 3.
There are just two pairs of vertices whose distance is 3: (2,5) and (3,5), so there are two ways to paint the tree to satisfy the condition: \lbrace 2,5\rbrace and \lbrace 3,5\rbrace .
Note that painting 2,3,5 does not satisfy the condition since the distance between Vertex 2 and Vertex 3 is 2.
Sample Input 2
4 1 2 1 3 1 4
Sample Output 2
4
The diameter is 2, and the four ways to paint the tree to satisfy the condition are: \lbrace 2,3\rbrace , \lbrace 2,4\rbrace , \lbrace 3,4\rbrace , \lbrace 2,3,4\rbrace .