题目详情题解（0）讨论（0）提交记录（0）

AT_kupc2019_j.Link-cut tworee

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定两棵 NN 个节点的以 11 为根的树，边有边权，保证两棵树的叶子节点个数相同。你要将两棵树上的叶子节点两两匹配，可以抽象为在一棵树中选一个叶子 uu，另一棵树中选一个叶子 vv，连边 (u,v,inf)(u,v,inf)。这样两棵树形成了一张图。

接着，你需要删掉一些边，使得图变成两棵树，并满足原先的两个 11 号节点在不同的树中。

求删去的边的最小边权和。

输入格式

第一行读入一个整数 NN，表示树的结点个数。

接下来 N−1N-1 行，每行三个整数 u,v,wu,v,w，表示第一棵树上 u,vu,v 之间有一条边权为 ww 的边。

接下来 N−1N-1 行，每行三个整数 u,v,wu,v,w，表示第二棵树上 u,vu,v 之间有一条边权为 ww 的边。

输出格式

一行一个整数，表示最小边权和。

输入输出样例

  • 输入#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

  • 输入#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

输入解题思路，AI测评打分。不知道怎么写?

首页