소들의 세 쌍

시간 제한2초메모리 제한1024 MB

요약

트리 모양으로 친구 관계를 맺은 N마리 소가 순서대로 떠나며, 떠난 소의 남은 친구들끼리 모두 친구가 됩니다. 각 출발 직전 친구 삼중항의 개수를 구합니다.

난이도: 어려움10점 중 8점
유형: 유니온 파인드, 트리, 그래프
정답자: 아직 제출이 없습니다

문제

처음에 FJ의 소 $N$ 마리( $2\le N\le 2\cdot 10^5$ ) 사이에 친구 관계가 $N-1$ 쌍 있으며, 이 관계는 트리를 이룬다. 소에는 $1$ 번부터 $N$ 번까지 번호가 붙어 있다. 소들은 한 마리씩 차례로 휴가를 떠난다. $i$ 일에 $i$ 번 소가 농장을 떠나면, 그 소의 친구 중 아직 농장에 남아 있는 소들끼리 모두 친구가 된다.

$1$ 부터 $N$ 까지의 각 $i$ 에 대해, $i$ 번 소가 떠나기 직전에 다음 조건을 만족하는 서로 다른 소 세 마리의 순서쌍 $(a,b,c)$ 가 몇 개인지 구하라. 세 소 $a,b,c$ 는 모두 휴가를 떠나지 않았고, $a$ 와 $b$ 가 친구이며 $b$ 와 $c$ 가 친구이다.

입력

첫째 줄에 $N$ 이 주어진다. 다음 $N-1$ 개의 줄에는 정수 $u_i$ 와 $v_i$ 가 주어진다. 이는 소 $u_i$ 와 소 $v_i$ 가 처음부터 친구라는 뜻이다( $1\le u_i,v_i\le N$ ).

출력

$i$ 를 $1$ 부터 $N$ 까지 바꿔 가며 구한 답을 한 줄에 하나씩 출력한다.

예제3

예제 1
입력
```
3
1 2
2 3
```
예상 출력
```
2
0
0
```
예제 2
입력
```
4
1 2
1 3
1 4
```
예상 출력
```
6
6
0
0
```
예제 3
입력
```
5
3 5
5 1
1 4
1 2
```
예상 출력
```
8
10
2
0
0
```