题目描述
Problem Description
Given a tree initially with \( n \) nodes.
On the \( i \)-th day, the \( i \)-th node of the tree will be deleted, and all nodes directly connected to node \( i \) will be connected pairwise with an edge. You need to find, before each deletion, the number of ordered triples \((a, b, c)\) such that there is an edge between \((a, b)\), an edge between \((b, c)\), and \( a \neq c \).
Input Format
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.
Output Format
The answers for \( i \) from 1 to \( N \) on separate lines.
Sample Input and Output
Input Sample #1
3
1 2
2 3
Output Sample #1
2
0
0
Input Sample #2
4
1 2
1 3
1 4
Output Sample #2
6
6
0
0
Input Sample #3
5
3 5
5 1
1 4
1 2
Output Sample #3
8
10
2
0
0
Notes
For the first sample:
\((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.
For the second sample:
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.
\( 2 \le N \le 2 \cdot 10^5 \), \( 1 \le u_i, v_i \le N \).
- Inputs 4-5: \( N \le 500 \).
- Inputs 6-10: \( N \le 5000 \).
- Inputs 11-20: No additional constraints.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分