← 返回题目列表

Codeforces · 2222/G

G. 树统计

中文机器翻译题面 查看原题

七风 - 咏叹调

给你一棵有 $$$n$$$ 个顶点的树。我们定义 值 路径的 一对 $$$(u,v)$$$ ($$$1\leq u\leq v\leq n$$$) 作为删除所有组件后最大组件的大小 边缘 在原始树中从 $$$u$$$ 到 $$$v$$$ 的路径上。

对于每个 $$$1\leq i\leq n$$$,你必须找到满足以下条件的对 $$$(u,v)$$$ 的数量: 值 路径的 是 $$$i$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n \leq 10^5$$$) — 顶点数。

然后是 $$$n-1$$$ 行,第 $$$i$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\leq u,v\leq n$$$) — 第 $$$i$$$ 条边连接的两个顶点。

保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 个整数,其中第 $$$i$$$ 表示满足其要求的不同对 $$$(u,v)$$$ 的数量 值 路径的 是 $$$i$$$。

示例

输入
复制

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

输出
复制

1
1 2
1 2 3
1 3 2 4
0 0 6 4 5
0 4 5 5 3 4 7
0 0 12 4 3 5 4 8

注意

在第一个测试用例中, $$$(1, 1)$$$ 对的 值 路径的 是 $$$1$$$。

在第二个测试用例中, 值 $$$(1, 1)$$$ 和 $$$(2, 2)$$$ 的 都是 $$$2$$$,因为不会删除任何边。的 $$$(1, 2)$$$对的 值 路径的 是$$$1$$$,因为边$$$(1, 2)$$$在树中从$$$1$$$到$$$2$$$的路径上,移除它后,剩下$$$2$$$分量,分别是$$$\{1\}$$$和$$$\{2\}$$$,并且最大组件的大小为$$$1$$$。

在第六个测试用例中,$$$(4, 6)$$$对的值为$$$3$$$,因为边$$$(3, 4)$$$、$$$(2, 3)$$$和$$$(2, 6)$$$在树中从$$$4$$$到$$$6$$$的路径上,删除它们后,将有剩下 $$$4$$$ 个分量,分别是 $$$\{1, 2, 5\}$$$、$$$\{3, 7\}$$$、$$$\{4\}$$$ 和 $$$\{6\}$$$,最大分量的大小为 $$$3$$$。