A16665. Rainbow Branch
编程题
NOI/NOI+/CTSC
知识点
题目描述
给定一棵有 $n$ 个顶点的树，你需要为每条边分配一种颜色。定义一次分配的“不便值”为任意两点之间路径上的颜色数的最大值。
你需要使用恰好 $k$ 种不同的颜色（每种颜色至少使用一次）给树的边染色，同时最小化染色的不便值。
请你计算所有 $k=1,2,\ldots,n-1$ 的最小不便值。
你需要使用恰好 $k$ 种不同的颜色（每种颜色至少使用一次）给树的边染色，同时最小化染色的不便值。
请你计算所有 $k=1,2,\ldots,n-1$ 的最小不便值。
输入格式
每个测试点包含若干测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 10^4$）。接下来是每组测试用例的描述。
每组测试用例的第一行包含一个正整数 $n$（$3\le n\le3\cdot10^5$），表示顶点数。
接下来的 $n-1$ 行，每行包含两个正整数 $u_i,v_i$（$1\le u_i,v_i\le n$），表示节点 $u_i$ 与 $v_i$ 之间有一条边。
保证输入中的边构成一棵树。
保证所有测试用例中 $n$ 的总和不超过 $3\cdot10^5$。
每组测试用例的第一行包含一个正整数 $n$（$3\le n\le3\cdot10^5$），表示顶点数。
接下来的 $n-1$ 行，每行包含两个正整数 $u_i,v_i$（$1\le u_i,v_i\le n$），表示节点 $u_i$ 与 $v_i$ 之间有一条边。
保证输入中的边构成一棵树。
保证所有测试用例中 $n$ 的总和不超过 $3\cdot10^5$。
输出格式
对于每个测试用例，输出一行 $n-1$ 个整数，第 $i$ 个整数表示当 $k=i$ 时最小的不便值。
输入输出样例
输入 #1
3 6 3 4 6 1 3 2 3 1 4 5 8 8 6 7 4 8 5 2 7 3 2 5 2 1 2 3 1 2 2 3
输出 #1
1 2 2 3 4 1 2 2 2 3 4 5 1 2
说明/提示
对于第一个测试用例，$k=1,2,\ldots,n-1$ 时可能的解如下：
