CF2222G Statistics on Tree

[Nanatsukaze - Aria](https://www.youtube.com/watch?v=P7ueDJG9IO4) 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 $ .