Distance Tree (easy version)

题意翻译

**本题与 CF1632E2 的唯一区别在于 $n$ 的数据范围。** 给定一个包含 $n$ 个节点的树，每条边的长度为 $1$。给出如下定义： - 定义 $d(v)$ 为从节点 $1$ 到节点 $v$ 的距离。 - 定义 $f(x)$ 为在任意两个点 $a,b$ 之间添加一个长度为 $x$ 的边后，$\max\limits_{1\leqslant v\leqslant n}d(v)$ 的最小值。 现在，对于所有的 $1\leqslant x\leqslant n$，求出 $f(x)$ 的值。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $2\leqslant n,\sum n\leqslant\bf 3000$。 Translated by Eason_AC 2022.1.31

题目描述

This version of the problem differs from the next one only in the constraint on $ n $ . A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The distance between two vertices is the minimum sum of weights on the path connecting them. You are given a weighted tree with $ n $ vertices, each edge has a weight of $ 1 $ . Denote $ d(v) $ as the distance between vertex $ 1 $ and vertex $ v $ . Let $ f(x) $ be the minimum possible value of $ \max\limits_{1 \leq v \leq n} \ {d(v)} $ if you can temporarily add an edge with weight $ x $ between any two vertices $ a $ and $ b $ $ (1 \le a, b \le n) $ . Note that after this operation, the graph is no longer a tree. For each integer $ x $ from $ 1 $ to $ n $ , find $ f(x) $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 3000 $ ). Each of the next $ n−1 $ lines contains two integers $ u $ and $ v $ ( $ 1 \le u,v \le n $ ) indicating that there is an edge between vertices $ u $ and $ v $ . It is guaranteed that the given edges form a tree. It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 3000 $ .

输出格式

For each test case, print $ n $ integers in a single line, $ x $ -th of which is equal to $ f(x) $ for all $ x $ from $ 1 $ to $ n $ .

输入输出样例

输入样例 #1

3
4
1 2
2 3
1 4
2
1 2
7
1 2
1 3
3 4
3 5
3 6
5 7

输出样例 #1

1 2 2 2 
1 1 
2 2 3 3 3 3 3

说明

 In the first testcase: - For $ x = 1 $ , we can an edge between vertices $ 1 $ and $ 3 $ , then $ d(1) = 0 $ and $ d(2) = d(3) = d(4) = 1 $ , so $ f(1) = 1 $ . - For $ x \ge 2 $ , no matter which edge we add, $ d(1) = 0 $ , $ d(2) = d(4) = 1 $ and $ d(3) = 2 $ , so $ f(x) = 2 $ .

题意翻译

**本题与 CF1632E2 的唯一区别在于 $n$ 的数据范围。** 给定一个包含 $n$ 个节点的树，每条边的长度为 $1$。给出如下定义： - 定义 $d(v)$ 为从节点 $1$ 到节点 $v$ 的距离。 - 定义 $f(x)$ 为在任意两个点 $a,b$ 之间添加一个长度为 $x$ 的边后，$\max\limits_{1\leqslant v\leqslant n}d(v)$ 的最小值。 现在，对于所有的 $1\leqslant x\leqslant n$，求出 $f(x)$ 的值。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $2\leqslant n,\sum n\leqslant\bf 3000$。 Translated by Eason_AC 2022.1.31