A16665 | $Rainbow Branch$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一棵有 $n$ 个顶点的树，你需要为每条边分配一种颜色。定义一次分配的“不便值”为任意两点之间路径上的颜色数的最大值。 你需要使用恰好 $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-1$ 个整数，第 $i$ 个整数表示当 $k=i$ 时最小的不便值。

输入 #1

输出 #1

1 2 2 3 4 
1 2 2 2 3 4 5 
1 2

C++ 编辑器

输入

输出