G. Статистика на дереве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Nanatsukaze - Aria

Вам дано дерево из $$$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$$$.