AT_abc401_f [ABC401F] Add One Edge 3

[problemUrl]: https://atcoder.jp/contests/abc401/tasks/abc401_f 给定两棵树： - 树 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 完成