AT_yahoo_procon2019_final_b Bonsai Grafting

高桥君购买了两盆盆栽，打算将它们在某一处连接进行嫁接。 每个盆栽可以分别表示为 $N$ 个顶点的树 $A$ 和 $M$ 个顶点的树 $B$。树 $A$ 的每条边连接顶点 $p_{A_i}$ 和顶点 $q_{A_i}$（$1 \leq i \leq N-1$）。树 $B$ 的每条边连接顶点 $p_{B_i}$ 和顶点 $q_{B_i}$（$1 \leq i \leq M-1$）。请注意，树 $A$ 的第 $i$ 个顶点和树 $B$ 的第 $i$ 个顶点是不同的顶点。 现在，考虑从树 $A$ 中选择一个顶点，与树 $B$ 中的一个顶点用一条边相连，得到一棵包含 $N+M$ 个顶点的新树。顶点的选择方式共有 $NM$ 种。对于这 $NM$ 种连接方式下得到的每棵树，计算其直径（即任意两点之间路径上的最大边数），并求这些直径的总和。

输入通过标准输入给出，格式如下： > $N$ $p_{A_1}$ $q_{A_1}$ … $p_{A_{N-1}}$ $q_{A_{N-1}}$ $M$ $p_{B_1}$ $q_{B_1}$ … $p_{B_{M-1}}$ $q_{B_{M-1}}$

输出所有 $NM$ 种连接方式下新树的直径之和。

## 限制条件 - $2 \leq N, M \leq 10^5$ - $1 \leq p_{A_i}, q_{A_i} \leq N$（$1 \leq i \leq N-1$） - $1 \leq p_{B_i}, q_{B_i} \leq M$（$1 \leq i \leq M-1$） - 给定的两个图均为树 - 输入均为整数 ## 样例解释 1 例如，将 $A$ 的顶点 $2$ 与 $B$ 的顶点 $1$ 用新边连接，得到一棵包含 $N+M$ 个顶点的树，此时直径为 $4$。 由 ChatGPT 4.1 翻译