分数: 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