CF1280C Jeremy Bearimy

欢迎来到这里！一切都很好。 你已经来到了“中间地带”，这是“好地方”和“坏地方”之间的区域。你被分配了一个任务，这个任务要么让人们更快乐，要么让他们永远受苦。 现在有 $k$ 对刚到新居住区的人。你需要将这 $2k$ 个人分别分配到 $2k$ 间房子中。每个人恰好住进一间房子，每间房子也恰好住进一人。 当然，在这个社区里，居民可以拜访朋友。这里有 $2k-1$ 条道路，每条道路连接两间房子。每条道路需要一定的时间才能通过，具体时间将在输入中给出。这个社区的设计保证了：从任意一间房子出发，到达另一间房子，恰好有一条不重复道路的路径。换句话说，以房子为顶点、道路为边的图是一棵树。 实际上，这 $k$ 对人是“灵魂伴侣”。我们将他们从 $1$ 到 $k$ 编号。我们用 $f(i)$ 表示第 $i$ 对灵魂伴侣互相拜访时所需的时间。 如前所述，你需要将这 $2k$ 个人分配到 $2k$ 间房子中。你有两个任务，分别来自“好地方”和“坏地方”的实体。具体如下： - 第一个任务，来自“好地方”：将人分配到房子中，使所有配对 $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$ 行包含三个用空格分隔的整数 $a_i, b_i, t_i$，表示第 $i$ 条道路连接第 $a_i$ 间和第 $b_i$ 间房子，且通过这条道路需要 $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$。

对于样例测试用例，最小和为 $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$。 由 ChatGPT 4.1 翻译