← 返回题目列表

AtCoder · abc401_f

I. 添加一条边 3

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

你有两棵树: 树 1 与 N_1 顶点编号 1 to N_1和树 2 与 N_2 顶点编号 1 to N_2。的 i树的第边 1 连接顶点 u_{1,i} 和 v_{1,i} 双向,并且 i树的第边 2 连接顶点 u_{2,i} 和 v_{2,i} 双向。

可以在顶点之间添加双向边 树的 i 树的 1 和顶点 j 树的 2 获得一棵树。 f(i,j) 是这棵树的直径。

查找 \displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} f(i,j).

这里,树的两个顶点之间的距离是在它们之间移动所必须使用的最小边数,树的直径是两个顶点之间的最大距离。

约束

  • 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
  • 两个给定的图都是树。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

例如,可以连接顶点 2 树的 1 和顶点 3 树的 2 获得一棵树的直径 5。因此, f(2,3) is 5.

总和 f(i,j) is 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