CF1223E.Paint the Tree

You are given a weighted tree consisting of $n$ vertices. Recall that a tree is a connected graph without cycles. Vertices $u_i$ and $v_i$ are connected by an edge with weight $w_i$.

Let's define the $k$-coloring of the tree as an assignment of exactly $k$ colors to each vertex, so that each color is used no more than two times. You can assume that you have infinitely many colors available. We say that an edge is saturated in the given $k$-coloring if its endpoints share at least one color (i.e. there exists a color that is assigned to both endpoints).

Let's also define the value of a $k$-coloring as the sum of weights of saturated edges.

Please calculate the maximum possible value of a $k$-coloring of the given tree.

You have to answer $q$ independent queries.

你将得到一棵包含 $n$ 个顶点的带权树。回忆一下，树是一种无环的连通图。顶点 $u_i$ 和 $v_i$ 之间由一条权重为 $w_i$ 的边相连。

我们定义树的一个 $k$-着色 为：为每个顶点恰好分配 $k$ 种颜色，且每种颜色至多被使用两次（即至多出现在两个顶点上）。你可以假设有无穷多种颜色可供使用。若某条边的两个端点至少共享一种颜色（即存在一种颜色同时被分配给了这两个端点），则称该边在给定的 $k$-着色下是饱和的。

此外，定义一个 $k$-着色的值为所有饱和边的权重之和。

请计算给定树的所有 $k$-着色中可能达到的最大值。

你需要回答 $q$ 个相互独立的询问。

The first line contains one integer $q$ ($1 \le q \le 5 \cdot 10^5$) – the number of queries.

The first line of each query contains two integers $n$ and $k$ ($1 \le n, k \le 5 \cdot 10^5$) — the number of vertices in the tree and the number of colors to assign to each vertex, respectively.

Each of the next $n - 1$ lines describes an edge of the tree. Edge $i$ is denoted by three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le w_i \le 10^5$) — the labels of vertices it connects and the weight of the edge. It is guaranteed that the given edges form a tree.

It is guaranteed that sum of all $n$ over all queries does not exceed $5 \cdot 10^5$.

第一行包含一个整数 $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$。

For each query print one integer — the maximum value of a $k$-coloring of the given tree.

对于每个查询，输出一个整数——给定树的 $k$-着色的最大值。

The tree corresponding to the first query in the example:

One of the possible $k$-colorings in the first example: $(1), (1), (2), (2)$, then the $1$-st and the $3$-rd edges are saturated and the sum of their weights is $8$.

The tree corresponding to the second query in the example:

One of the possible $k$-colorings in the second example: $(1, 2), (1, 3), (2, 4), (5, 6), (7, 8), (3, 4), (5, 6)$, then the $1$-st, $2$-nd, $5$-th and $6$-th edges are saturated and the sum of their weights is $14$.

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

第一个示例中一种可能的 $k$-着色方案：$(1), (1), (2), (2)$，此时第 $1$ 条和第 $3$ 条边被饱和，其权重之和为 $8$。

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

第二个示例中一种可能的 $k$-着色方案：$(1, 2), (1, 3), (2, 4), (5, 6), (7, 8), (3, 4), (5, 6)$，此时第 $1$、$2$、$5$ 和 $6$ 条边被饱和，其权重之和为 $14$。