Triples of Cows
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?
(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.
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⋅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.
SCORING:
- Inputs 4-5: N≤500
- Inputs 6-10: N≤5000
- Inputs 11-20: No additional constraints.
Problem credits: Aryansh Shrivastava, Benjamin Qi
Source: USA Computing Olympiad.
Input Format
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 Format
The answers for i from 1 to N on separate lines.