← 返回题目列表

AtCoder · kupc2019_j

J. 链接剪切二重奏

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

配点 : 400 点

問題文

从前,有一个樵夫,名叫和真。

和真君是 2 一 N 有根顶点树 我有 T_1, T_2 。 T_1, T_2 的根都是一个顶点 1 和T_1, T_2 具有相同数量的叶子。 此外,在两棵树中,顶点 1 不是叶子。 连接

T_1 的 i 边是边界 a_i 和 b_i , 它是一条无向边,权重为w_i 。 同样地 它是一条无向边,权重为 T_2 的 i 边是边界 c_i 和 d_i , 它是一条无向边,权重为v_i 。 我决定结合

和真君是 T_1, T_2 并使用以下步骤创建两棵新树。 将

  • T_1 和 T_2 的叶子一一对应,并收缩对应的叶子,1 创建两个图表。
  • 之后,从您创建的图中删除一些边,使其满足以下三个条件。
    • T_1 的顶点 1 和 T_2 的顶点 1 未连接。
    • T_1 的顶点 1 所属的连接组件成为一棵树。T_2 的顶点 1 也是如此。
    • 任何顶点都是 它与 T_1 的顶点 1 或 如果 T_2 的顶点 1 连接。

当移除边缘时,会消耗移除边缘的权重之和的能量。 求和真君能够达到的最低能量消耗。

制約

  • 3 \leq N \leq 10^5
  • 1 \leq a_i, b_i, c_i, d_i \leq N
  • 1 \leq w_i, v_i \leq 10^9
  • 2 两个图都是树。
  • 2 两个图的叶子数相同
  • 2 在每个图中,顶点 1 不是叶子
  • 所有输入均以整数形式给出

入力

输入将以以下格式从标准输入提供。

N
a_1 b_1 w_1
a_2 b_2 w_2
:
a_{N - 1} b_{N - 1} w_{N - 1}
c_1 d_1 v_1
c_2 d_2 v_2
:
c_{N - 1} d_{N - 1} v_{N - 1}

出力

输出可实现的最小能耗。


入力例 1

5
1 2 1
1 5 3
2 3 4
2 4 6
1 2 8
1 3 7
2 4 2
2 5 5

出力例 1

6

「T_1 叶子 x 和 T_2 叶子 y “到”(x, y) 。 和真君第一 使用 (3, 3), (4, 4), (5, 5) 将其缩小,然后删除上图中的虚线边缘。 此时消耗的能量为 6 ,这是最小值。


入力例 2

6
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
1 6 1000000000
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
1 6 1000000000

出力例 2

5000000000

入力例 3

7
1 2 8613
3 6 91
2 5 20238
3 7 5018
1 3 10453
2 4 7580
3 7 123
2 5 24095
1 2 6957
2 4 13166
1 3 72
2 6 2444

出力例 3

7625