← 返回题目列表

AtCoder · yahoo_procon2019_final_b

B. 盆景嫁接

中文机器翻译题面 查看原题

配点 : 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