← 返回题目列表

Codeforces · 1223/E

E. 画树

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

给你一个由 $$$n$$$ 个顶点组成的加权树。回想一下,树是一个没有循环的连通图。顶点 $$$u_i$$$ 和 $$$v_i$$$ 通过权重为 $$$w_i$$$ 的边连接。

让我们将树的 $$$k$$$ 着色定义为为每个顶点精确分配 $$$k$$$ 颜色,以便每种颜色使用不超过两次。您可以假设您有无限多种可用颜色。如果一条边的端点至少共享一种颜色(即存在分配给两个端点的颜色),则我们说该边在给定的 $$$k$$$ 着色中饱和。

我们还将 $$$k$$$ 着色的值定义为饱和边缘的权重之和。

请计算给定树的 $$$k$$$ 着色的最大可能值。

您必须回答 $$$q$$$ 独立查询。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) – 查询数。

每个查询的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 5 \cdot 10^5$$$) - 分别是树中的顶点数和分配给每个顶点的颜色数。

接下来的 $$$n - 1$$$ 行描述了树的一条边。边 $$$i$$$ 由三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ 表示 ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$, $$$1 \le w_i \le 10^5$$$) - 它连接的顶点的标签和权重边缘。保证给定的边形成一棵树。

保证所有查询的所有 $$$n$$$ 之和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个查询,打印一个整数 - 给定树的 $$$k$$$ 着色的最大值。

示例

输入 #1

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

输出 #1

8
14

注意

示例中第一个查询对应的树:

第一个示例中可能的 $$$k$$$-着色之一:$$$(1), (1), (2), (2)$$$,然后 $$$1$$$-st 和 $$$3$$$-rd 边饱和,它们的权重总和为 $$$8$$$。

示例中第二个查询对应的树:

第二个示例中可能的 $$$k$$$-着色之一:$$$(1, 2), (1, 3), (2, 4), (5, 6), (7, 8), (3, 4), (5, 6)$$$,然后是 $$$1$$$-st、$$$2$$$-nd、$$$5$$$-th第 $$$6$$$ 条边已饱和,其权重之和为 $$$14$$$。