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