CF2222G.Statistics on Tree

Nanatsukaze - Aria

You are given a tree of $ n $ vertices. We define the value of a pair $ (u,v) $ ( $ 1\leq u\leq v\leq n $ ) as the size of the largest component after removing all edges on the path from $ u $ to $ v $ in the original tree.

For every $ 1\leq i\leq n $ , you have to find the number of pairs $ (u,v) $ satisfying that its value is $ i $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1\leq n \leq 10^5 $ ) — the number of vertices.

Then $ n-1 $ lines follow, the $ i $ -th line containing two integers $ u $ and $ v $ ( $ 1\leq u,v\leq n $ ) — the two vertices that the $ i $ -th edge connects.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5\cdot 10^5 $ .

For each test case, output $ n $ integers, the $ i $ -th of which denotes the number of distinct pairs $ (u,v) $ satisfying its value is $ i $ .

In the first test case, the value of pair $ (1, 1) $ is $ 1 $ .

In the second test case, the values of pairs $ (1, 1) $ and $ (2, 2) $ are both $ 2 $ , because no edges will be removed. The value of pair $ (1, 2) $ is $ 1 $ , because edge $ (1, 2) $ is on the path from $ 1 $ to $ 2 $ in the tree, and after removing it, there will be $ 2 $ components left, which are $ {1} $ and $ {2} $ , and the size of the largest component is $ 1 $ .

In the sixth test case, the value of pair $ (4, 6) $ is $ 3 $ , because edges $ (3, 4) $ , $ (2, 3) $ , and $ (2, 6) $ are on the path from $ 4 $ to $ 6 $ in the tree, and after removing them, there will be $ 4 $ components left, which are $ {1, 2, 5} $ , $ {3, 7} $ , $ {4} $ , and $ {6} $ , and the size of the largest component is $ 3 $ .