Problems
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?
Input
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)
Output
The answers for i from 1 to N on separate lines.
Example #1
3
1 2
2 3
2
0
0
Example #2
4
1 2
1 3
1 4
6
6
0
0
Example #3
5
3 5
5 1
1 4
1 2
8
10
2
0
0
Hint
Source
USACO 2023 US Open Platinum
You must sign in to write code.