8231: [yosupo] Tree - Frequency Table of Tree Distance
[Creator : ]
Description
Given a tree with $N$ vertices, where the $i$-th edge connects vertex $a_i$ and $b_i$. Denote by $x_i$ the number of pairs $(u, v)$ such that $\mathrm{dist}(u, v) = i$. Find $x_i$ for each $i = 1, 2, \cdots, N - 1$.
$\mathrm{dist}(u, v)$ denotes the number of edges on the unique path between vertex $u$ and $v$.
$\mathrm{dist}(u, v)$ denotes the number of edges on the unique path between vertex $u$ and $v$.
Input
$N$
$a_0$ $b_0$
$a_1$ $b_1$
$\vdots$
$a_{N-2}$ $b_{N-2}$
$a_0$ $b_0$
$a_1$ $b_1$
$\vdots$
$a_{N-2}$ $b_{N-2}$
Output
$x_1$ $x_2$ $\ldots$ $x_{N-1}$
Constraints
$1 \leq N \leq 200,000$
$0 \leq a_i, b_i < N$
$a_i \neq b_i$
$0 \leq a_i, b_i < N$
$a_i \neq b_i$
Sample 1 Input
8
0 1
1 2
2 3
1 4
4 7
1 5
2 6
Sample 1 Output
7 10 9 2 0 0 0