28027번 - Triples of Cows 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 18 | 4 | 4 | 50.000% |
문제
There are initially $N-1$ pairs of friends among FJ's $N$ ($2\le N\le 2\cdot 10^5$) cows labeled $1\dots N$, forming a tree. The cows are leaving the farm for vacation one by one. On day $i$, the $i$th cow leaves the farm, and then all pairs of the $i$th cow's friends still present on the farm become friends.
For each $i$ from $1$ to $N$, just before the $i$th cow leaves, how many ordered triples of distinct cows $(a,b,c)$ are there such that none of $a,b,c$ are on vacation, $a$ is friends with $b$, and $b$ is friends with $c$?
입력
The first line contains $N$.
The next $N-1$ lines contain two integers $u_i$ and $v_i$ denoting that cows $u_i$ and $v_i$ are initially friends ($1\le u_i,v_i\le N$).
출력
The answers for $i$ from $1$ to $N$ on separate lines.
예제 입력 1
3 1 2 2 3
예제 출력 1
2 0 0
$(1,2,3)$ and $(3,2,1)$ are the triples just before cow $1$ leaves.
After cow $1$ leaves, there are less than $3$ cows left, so no triples are possible.
예제 입력 2
4 1 2 1 3 1 4
예제 출력 2
6 6 0 0
At the beginning, cow $1$ is friends with all other cows, and no other pairs of cows are friends, so the triples are $(a, 1, c)$ where $a, c$ are different cows from $\{2, 3, 4\}$, which gives $3 \cdot 2 = 6$ triples.
After cow $1$ leaves, the remaining three cows are all friends, so the triples are just those three cows in any of the $3! = 6$ possible orders.
After cow $2$ leaves, there are less than $3$ cows left, so no triples are possible.
예제 입력 3
5 3 5 5 1 1 4 1 2
예제 출력 3
8 10 2 0 0