문제
There are initially N−1 pairs of friends among FJ's N (2≤N≤2⋅105) cows labeled 1…N, forming a tree. The cows are leaving the farm for vacation one by one. On day i, the ith cow leaves the farm, and then all pairs of the ith cow's friends still present on the farm become friends.
For each i from 1 to N, just before the ith 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 ui and vi denoting that cows ui and vi are initially friends(1≤ui,vi≤N)
출력
The answers for i from 1 to N on separate lines.
예제 #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
힌트
출처
USACO 2023 US Open Platinum
로그인해야 코드를 작성할 수 있어요.