platinum_Triples_of_Cows — USACO US_Open_Contest
Task type: batch | Time limit: 2 s | Memory limit: 256 MB | Difficulty: 25
Algorithms: union-find, data structures, mathematics, implementation, biconnected component

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$?
INPUT FORMAT (input arrives from the terminal / stdin):
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$).
OUTPUT FORMAT (print output to the terminal / stdout):
The answers for $i$ from $1$ to $N$ on separate lines.
SAMPLE INPUT:
3
1 2
2 3
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
4
1 2
1 3
1 4
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
5
3 5
5 1
1 4
1 2
SAMPLE OUTPUT:
8
10
2
0
0
SCORING:
Inputs 4-5: $N\le 500$
Inputs 6-10: $N\le 5000$
Inputs 11-20: No additional constraints.
Problem credits: Aryansh Shrivastava, Benjamin Qi

Starter code: