P3820.第3题-无根树
题目内容
TK 有一棵由 n 个节点 n−1 条边构成的无根树。给定一个整数上限 m 。你需要为每个节点填入一个不超过 m 的正整数。要求任意两条相邻的节点权值不同。请最小化所有节点权值之和，并输出这个最小值。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦104) 代表数据组数，每组测试数据描述如下：
-
第一行输入两个整数 n,m(1≦n≦2×105;2≦m≦109)，表示节点数与权值上限;
-
此后 n−1 行，每行输入两个整数 u,v(1≦u,v≦n;u=v) ，表示一条无向边连接 u 与 v ;
除此之外，保证单个测试文件的 n 之和不超过 2×105 ，并且给定的边集构成一棵树。
输出描述
对于每一组测试数据，新起一行，输出一个整数，表示在满足相邻节点权值不同的条件下，所有节点权值和的最小值。
样例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 。
