8201: USACO 2023 US Open Contest, Platinum Problem 3. Triples of Cows
[Creator : ]
Description
There are initially N−1 pairs of friends among FJ's $N\ (2≤N≤2⋅10^5)$ cows labeled 1…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?
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
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≤u_i,v_i≤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≤u_i,v_i≤N)$.
Output
The answers for i from 1 to N on separate lines.
Sample 1 Input
3
1 2
2 3
Sample 1 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.
After cow 1 leaves, there are less than 3 cows left, so no triples are possible.
Sample 2 Input
4
1 2
1 3
1 4
Sample 2 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⋅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.
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 3 Input
5
3 5
5 1
1 4
1 2
Sample 3 Output
8
10
2
0
0
HINT
相同题目：USACO Platinum。