给你一棵有 $$$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$$$。
示例
输入复制
7121 231 21 341 22 33 451 22 32 42 573 41 52 32 65 27 382 13 24 15 36 27 68 1
输出复制
11 21 2 31 3 2 40 0 6 4 50 4 5 5 3 4 70 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$$$。