题目描述

题目译自 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

$(1,2,3)$ 和 $(3,2,1)$ 是就在奶牛 $1$ 离开之前的三元组。

在奶牛 $1$ 离开后，剩下的奶牛不足三头，所以不可能有三元组。

4
1 2
1 3
1 4

6
6
0
0

在最开始，奶牛 $1$ 是所有其他奶牛的朋友，并且除此之外奶牛间没有朋友关系，所以三元组形如 $(a,1,c)$，其中 $a,c$ 是从 $\{2,3,4\}$ 中选出的不同的两头奶牛，因此形成了 $3\cdot 2=6$ 个三元组。

在奶牛 $1$ 离开后，剩下的三头奶牛都成为了朋友，所以三元组仍然是这三头奶牛以 $3!=6$ 种顺序任意排列形成的。

在奶牛 $2$ 离开后，剩下的奶牛不足三头，所以不可能有三元组。

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 组数据：无附加限制