题目描述

题目译自 USACO 2023 US Open Contest, Platinum Problem 3. Triples of Cows

最初 FJ 有 $N\ (2\le N\le 2\cdot 10^5)$ 头奶牛，这些奶牛的编号为 $1\ldots N$，这些奶牛中有 $N-1$ 对朋友，朋友关系形成了一棵树。这些奶牛会一个接一个离开农场去度假。在第 $i$ 天，奶牛 $i$ 会离开农场，然后奶牛 $i$ 的朋友中目前还在农场的那些会两两结为朋友。

对于 $1$ 到 $N$ 的每个 $i$，就在奶牛 $i$ 离开之前，有多少个不同奶牛的有序三元组 $(a,b,c)$ 满足 $a,b,c$ 三头奶牛都没去度假，且 $a$ 和 $b$ 是朋友，$b$ 和 $c$ 是朋友？

输入格式

第一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数 $u_i$ 和 $v_i\ (1\le u_i,v_i\le N)$，表示最初奶牛 $u_i$ 和奶牛 $v_i$ 是朋友。

输出格式

输出 $N$ 行，第 $i$ 行输出对于第 $i$ 天的答案。

3
1 2
2 3

2
0
0

4
1 2
1 3
1 4

6
6
0
0

5
3 5
5 1
1 4
1 2

8
10
2
0
0

数据范围与提示

• 4-5 组数据：$N\le 500$
• 6-10 组数据：$N\le 5000$
• 11-20 组数据：无附加限制