欢迎!一切都很好。
你已经到达了中位,即好地方和坏地方之间的地方。你被分配的任务要么会让人们更快乐,要么永远折磨他们。
您有一份已抵达新有人居住的社区的 $$$k$$$ 人的列表。您需要将 $$$2k$$$ 中的每个人分配到 $$$2k$$$ 房屋中的一所。每个人将恰好是一所房子的居民,而每所房子也将恰好有一名居民。
当然,在附近,拜访朋友是可以的。有 $$$2k - 1$$$ 条道路,每条道路连接两栋房屋。走过一条路需要一些时间。我们将指定输入所需的时间。该社区的设计方式是,从任何人的房子里,都可以通过一系列不同的道路到达任何其他房子。换句话说,以房屋为顶点、以道路为边的图就是一棵树。
事实是,这些 $$$k$$$ 的人实际上是灵魂伴侣。我们对它们进行索引,从 $$$1$$$ 到 $$$k$$$。我们用 $$$f(i)$$$ 表示第 $$$i$$$ 一对灵魂伴侣去对方家所花费的时间。
正如我们之前所说,您需要将每个 $$$2k$$$ 人分配到 $$$2k$$$ 房屋中的一所。您有两项任务,一项来自好地方的实体,一项来自坏地方的实体。他们在这里:
- 来自 The Good Place 的第一个任务是将人们分配到房屋中,以使所有对 $$$i$$$ 的 $$$f(i)$$$ 总和最小化。让我们将这个最小总和定义为$$$G$$$。这确保了灵魂伴侣可以轻松有效地互相拜访;
- 来自坏地方的第二个任务是将人们分配到房屋中,以使所有对 $$$i$$$ 的 $$$f(i)$$$ 总和最大化。我们将这个最大总和定义为$$$B$$$。这使得灵魂伴侣很难互相拜访。
$$$G$$$ 和 $$$B$$$ 的值是多少?
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) 表示测试用例的数量。接下来的几行包含测试用例的描述。
每个测试用例的第一行包含一个整数 $$$k$$$ 表示人对的数量 ($$$1 \le k \le 10^5$$$)。接下来的 $$$2k - 1$$$ 行描述了道路;其中第 $$$i$$$-th 包含三个空格分隔的整数 $$$a_i, b_i, t_i$$$,这意味着第 $$$i$$$-th 条道路连接第 $$$a_i$$$-th 和 $$$b_i$$$-th 房屋,并且需要花费 $$$t_i$$$ 时间单位来遍历 ($$$1 \le a_i, b_i \le 2k$$$、$$$a_i \neq b_i$$$、$$$1 \le t_i \le 10^6$$$)。保证给定的道路定义树结构。
保证单个文件中$$$k$$$的总和最多为$$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行包含两个空格分隔的整数 $$$G$$$ 和 $$$B$$$。
示例
输入 #1
2 3 1 2 3 3 2 4 2 4 3 4 5 6 5 6 5 2 1 2 1 1 3 2 1 4 3
输出 #1
15 33 6 6
注意
对于示例测试用例,我们的最小总和等于 $$$G = 15$$$。实现此目的的一种方法是使用以下分配:
- 第一对人被分配到房子 $$$5$$$ 和 $$$6$$$,给我们 $$$f(1) = 5$$$;
- 第二对人被分配到房子 $$$1$$$ 和 $$$4$$$,给我们 $$$f(2) = 6$$$;
- 第三对人被分配到房子 $$$3$$$ 和 $$$2$$$,给我们 $$$f(3) = 4$$$。
请注意,$$$f(i)$$$ 的总和为 $$$5 + 6 + 4 = 15$$$。
我们还有一个最大金额等于 $$$B = 33$$$。实现此目的的一种方法是使用以下分配:
- 第一对人被分配到房子 $$$1$$$ 和 $$$4$$$,给我们 $$$f(1) = 6$$$;
- 第二对人被分配到房子 $$$6$$$ 和 $$$2$$$,给我们 $$$f(2) = 14$$$;
- 第三对人被分配到房子 $$$3$$$ 和 $$$5$$$,给我们 $$$f(3) = 13$$$。
请注意,$$$f(i)$$$ 的总和为 $$$6 + 14 + 13 = 33$$$。