配点 : 700 点
問題文
高桥君要购买盆栽 2 棵,并打算在一个地方进行嫁接。
每棵盆栽, N 顶点树 在 A 和 还给出了M 顶点树 在 B 可以表示为。树 A 条边为边 p_{A_i} 与边缘 q_{A_i} (1 ≤ i ≤ N-1) 进行连接。 树 B 条边为边 p_{B_i} 与边缘 q_{B_i} (1 ≤ i ≤ M-1) 进行连接(注意,树 A 的顶点 从 i 和树 B 的顶点 从 i 是不同的顶点)。 用边连接
木 A 的顶点 从 1 个和 B 的顶点 从 1 个树, 1 个 N+M 顶点的树可以这样构造。 选择顶点的方式总共有 NM 种。这个 NM 对每棵树,计算直径(即2 点之间的边数的最大值),然后求和。
制約
- 2 ≤ N, M ≤ 10^5
- 1 ≤ p_{A_i}, q_{A_i} ≤ N (1 ≤ i ≤ N-1)
- 1 ≤ p_{B_i}, q_{B_i} ≤ M (1 ≤ i ≤ M-1)
- 给出 它是 2 个图分别是树
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
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 输出每棵树的直径总和。
入力例 1
4 1 2 2 3 3 4 2 1 2
出力例 1
36
例如, A 的顶点 从 2 和 按字典顺序比较 B 的顶点 从 1 用新的边连接,N+M 制作一个顶点树,其直径为 4 。 对于
入力例 2
5 1 2 1 3 1 4 1 5 3 1 2 2 3
出力例 2
67