Frequency Table of Tree Distance

AC一覧

Problem Statement問題文

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$.

$N$ 頂点の木があります。辺は $(a_i, b_i)$ です。各 $i = 1, 2, \cdots, N - 1$ について、$\mathrm{dist}(u, v) = i$ となる頂点対 $u, v (u < v)$ の個数 $x_i$ を求めてください。

$\mathrm{dist}(u, v)$ は頂点 $u, v$ をつなぐパスの辺数です。

Constraints制約

• $1 \leq N \leq 200{,}000$
• $a_i \neq b_i$

Input入力

$N$
$a_0$ $b_0$
$a_1$ $b_1$
$\vdots$
$a_{N-2}$ $b_{N-2}$

Output出力

$x_1$ $x_2$ $\ldots$ $x_{N-1}$

Sampleサンプル

# 1

8
0 1
1 2
2 3
1 4
4 7
1 5
2 6
7 10 9 2 0 0 0

Timelimit: 10 secs

Before submitting, please confirm terms and conditions