给你一个由 $$$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$$$。