/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
頂点に 1 から N_1 までの番号が付いた N_1 頂点の木 1 と、頂点に 1 から N_2 までの番号が付いた N_2 頂点の木 2 が与えられます。木 1 の i 番目の辺は木 1 の頂点 u_{1,i} と v_{1,i} を双方向に結び、木 2 の i 番目の辺は木 2 の頂点 u_{2,i} と v_{2,i} を双方向に結んでいます。
木 1 の頂点 i と、木 2 の頂点 j を双方向に結ぶ辺を追加すると一つの木が得られます。この木の直径を f(i,j) と定めます。
\displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} f(i,j) を求めてください。
ただし、木の 2 頂点の間の距離は一方から他方へ移動するときに用いる辺の本数の最小値であり、 木の直径は任意の 2 頂点の間の距離の最大値として定められます。
制約
- 1\leq N_1,N_2\leq 2\times 10^{5}
- 1\leq u_{1,i},v_{1,i}\leq N_1
- 1\leq u_{2,i},v_{2,i}\leq N_2
- 入力されるグラフは共に木
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N_1
u_{1,1} v_{1,1}
\vdots
u_{1,N_1-1} v_{1,N_1-1}
N_2
u_{2,1} v_{2,1}
\vdots
u_{2,N_2-1} v_{2,N_2-1}
出力
答えを出力せよ。
入力例 1
3 1 3 1 2 3 1 2 3 1
出力例 1
39
例えば木 1 の頂点 2 と木 2 の頂点 3 を結んで得られる木の直径は 5 です。よって f(2,3) は 5 となります。
f(i,j) の総和は 39 です。
入力例 2
7 5 6 1 3 5 7 4 5 1 6 1 2 5 5 3 2 4 2 3 5 1
出力例 2
267
Score : 500 points
Problem Statement
You are given two trees: tree 1 with N_1 vertices numbered 1 to N_1, and tree 2 with N_2 vertices numbered 1 to N_2. The i-th edge of tree 1 connects vertices u_{1,i} and v_{1,i} bidirectionally, and the i-th edge of tree 2 connects vertices u_{2,i} and v_{2,i} bidirectionally.
One can add a bidirectional edge between vertex i of tree 1 and vertex j of tree 2 to obtain a single tree. Let f(i,j) be the diameter of this tree.
Find \displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} f(i,j).
Here, the distance between two vertices of a tree is the minimum number of edges that must be used to move between them, and the diameter of a tree is the maximum distance between two vertices.
Constraints
- 1 \le N_1, N_2 \le 2 \times 10^{5}
- 1 \le u_{1,i}, v_{1,i} \le N_1
- 1 \le u_{2,i}, v_{2,i} \le N_2
- Both given graphs are trees.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N_1
u_{1,1} v_{1,1}
\vdots
u_{1,N_1-1} v_{1,N_1-1}
N_2
u_{2,1} v_{2,1}
\vdots
u_{2,N_2-1} v_{2,N_2-1}
Output
Print the answer.
Sample Input 1
3 1 3 1 2 3 1 2 3 1
Sample Output 1
39
For example, one can connect vertex 2 of tree 1 and vertex 3 of tree 2 to obtain a tree of diameter 5. Thus, f(2,3) is 5.
The sum of f(i,j) is 39.
Sample Input 2
7 5 6 1 3 5 7 4 5 1 6 1 2 5 5 3 2 4 2 3 5 1
Sample Output 2
267