#172 Finding Triangular Stars

Loading problem...

Preparing the statement, recent submissions, and submit form.

#172 Finding Triangular Stars | DOJ

Statement

양의 정수 $K$ 에 대해, 크기가 $K$ 인 삼각별은 하나의 가운데 정점에서 시작하는 길이 $K$ 의 단순 경로 $3$ 개가 가운데 정점만 공유하고 뻗어 나가는 모양이다.

정확히는, 트리의 정점 $c$ 를 가운데 정점으로 하는 크기 $K$ 의 삼각별이 존재한다는 것은 $c$ 에서 시작하는 길이 $K$ 의 단순 경로 $3$ 개를 고를 수 있고, 이 세 경로가 정점 $c$ 를 제외한 어떤 정점도 공유하지 않는다는 뜻이다.

$N$ 개의 정점을 가진 트리가 입력으로 주어진다. 주어진 트리 위에서 찾을 수 있는 서로 다른 삼각별의 개수를 크기별로 구하여라.

두 삼각별의 크기가 같고 가운데 정점이 같다면 같은 삼각별로 본다. 즉, 같은 가운데 정점과 같은 크기에 대해 가능한 경로 $3$ 개의 선택 방법이 여러 가지여도 하나만 센다.

입력은 다음과 같은 형식으로 주어진다.

$N$ $U_1\ V_1$ $U_2\ V_2$ $\vdots$ $U_{N-1}\ V_{N-1}$

크기가 각각 $1,2,3,\ldots,N$ 인 서로 다른 삼각별의 개수를 공백으로 구분하여 출력한다.

#	Score	Constraints
1	100	전체 제약을 만족한다.

Sample 1

Input

Output

정점이 하나뿐이므로 삼각별은 존재하지 않는다.

Sample 2

Input

Output

1 0 0 0

정점 $1$ 을 가운데 정점으로 하는 크기 $1$ 의 삼각별이 존재한다.

Sample 3

Input

Output

1 1 0 0 0 0 0

정점 $1$ 을 가운데 정점으로 하는 크기 $1$ 의 삼각별과 크기 $2$ 의 삼각별이 존재한다.