\(N\)개의 정점으로 이루어진 트리가 주어진다. 모든 간선의 길이는 \(1\)이며, 두 정점 사이의 거리는 두 정점을 잇는 경로의 간선 수이다.

각 거리 \(d = 1, 2, \dots, N-1\) 에 대해, 거리가 정확히 \(d\)인 서로 다른 정점 쌍의 개수를 구하라. 쌍은 순서를 구분하지 않는다(즉 \(\{u, v\}\)와 \(\{v, u\}\)는 같은 쌍).

정점 수가 많으므로 모든 쌍을 직접 세는 것보다 빠른 방법이 필요하다.

\(1 \le N \le 40{,}000\)

주어지는 그래프는 항상 트리이다.

첫 줄에 정점 수 \(N\)이 주어진다.

이어서 \(N-1\)개의 줄에 각각 두 정수 \(u\), \(v\)가 주어지며 정점 \(u\)와 \(v\)를 잇는 간선을 나타낸다.

한 줄에 \(N-1\)개의 정수를 공백으로 구분하여 출력한다. \(d\)번째 수는 거리가 정확히 \(d\)인 정점 쌍의 수이다. (\(N = 1\)이면 빈 줄을 출력한다.)

riseoj 작성

출처 Original