解题思路

• 核心观察 树是二分图，把树按根 1 做 BFS/DFS，按层数奇偶划分为两部分（偶层集合 A、奇层集合 B）。由于相邻点层数相反，天然满足 A—B 之间的边相连。

• 为什么只用 1 和 2 就够了 题目给出上界 $m\ge 2$。对任意节点，只需与父节点不同即可；若父为 1，则该点取 2；否则取 1。使用更大的数不会更优（只会让总和更大），因此最优解一定只使用 $\{1,2\}$。

• 如何最小化总和 给定二分划分 $(A,B)$，两种赋值：

题目内容

TK 有一棵由 $n$ 个节点 $n-1$ 条边构成的无根树。给定一个整数上限 $m$ 。你需要为每个节点填入一个不超过 $m$ 的正整数。要求任意两条相邻的节点权值不同。请最小化所有节点权值之和，并输出这个最小值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦ T ≦ 10^4)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入两个整数 $n,m(1 ≦n≦2×10^5;2≦m ≦ 10^9)$，表示节点数与权值上限;

• 此后 $n -1$ 行，每行输入两个整数 $u,v(1 ≦ u,v≦ n;u≠ v)$ ，表示一条无向边连接 $u$ 与 $v$ ;

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ ，并且给定的边集构成一棵树。

输出描述

对于每一组测试数据，新起一行，输出一个整数，表示在满足相邻节点权值不同的条件下，所有节点权值和的最小值。

样例1

输入

2
1 5
3 2
1 2
2 3

输出

1
4

说明

● 第一组：只有一个节点，取 $1$ 即可，最小和为 $1$ ;

● 第二组：链 $1-2-3$，可令节点 {$1,3$} 取 $1$ ，节点 $2$ 取 $2$ ，总和为 $1+2+1= 4$ 。