AT_abc401_f.[ABC401F] Add One Edge 3

给定两棵树：

• 树 1 包含 $N_1$ 个顶点，编号为 $1$ 到 $N_1$
• 树 2 包含 $N_2$ 个顶点，编号为 $1$ 到 $N_2$

树 1 的第 $i$ 条边双向连接顶点 $u_{1,i}$ 和 $v_{1,i}$，树 2 的第 $i$ 条边双向连接顶点 $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)$ 的值。

其中：

• 两顶点之间的距离定义为它们之间最短路径的边数
• 树的直径定义为所有顶点对之间距离的最大值

输入通过标准输入给出，格式如下：

$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 \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$
• 输入的两张图都是树
• 输入的所有数值均为整数

样例解释 1

例如，当连接树 1 的顶点 2 和树 2 的顶点 3 时，得到的新树直径为 5，因此 $f(2,3)=5$。所有 $f(i,j)$ 的总和为 39。

翻译由 DeepSeek V3 完成