Triples of Cows

题目描述

FJ 的 $N$ 头奶牛（$2\le N\le 2\cdot 10^5$）编号为 $1\dots N$，初始时有 $N-1$ 对朋友关系，构成一棵树。奶牛将按顺序一头一头离开农场去度假。在第 $i$ 天，第 $i$ 头奶牛离开农场；随后，这头奶牛在农场中仍然存在的所有朋友两两之间都会成为朋友。

对每个 $i$（从 $1$ 到 $N$），在第 $i$ 头奶牛离开之前，有多少个互不相同的奶牛的有序三元组 $(a,b,c)$ 满足：$a,b,c$ 都未去度假，且 $a$ 与 $b$ 是朋友，$b$ 与 $c$ 是朋友？

输入格式

第一行包含 $N$。 接下来 $N-1$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示奶牛 $u_i$ 与奶牛 $v_i$ 在初始时是朋友（$1\le u_i,v_i\le N$）。

输出格式

将 $i$ 从 $1$ 到 $N$ 的答案分别输出，每个答案一行。

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

提示

$(1,2,3)$ 和 $(3,2,1)$ 是在奶牛 $1$ 离开之前的三元组。 在奶牛 $1$ 离开后，剩下的奶牛少于 $3$ 头，因此不可能有三元组。

一开始，奶牛 $1$ 与所有其他奶牛都是朋友，而其他奶牛之间都不是朋友，因此三元组为 $(a, 1, c)$，其中 $a,c$ 是从 $\{2, 3, 4\}$ 中选取的不同奶牛，总数为 $3 \cdot 2 = 6$ 个三元组。 在奶牛 $1$ 离开后，剩下的三头奶牛彼此都是朋友，因此三元组就是这三头奶牛的任意排列，共有 $3! = 6$ 种可能的顺序。 在奶牛 $2$ 离开后，剩下的奶牛少于 $3$ 头，因此不可能有三元组。

计分： 输入 4-5：$N\le 500$ 输入 6-10：$N\le 5000$ 输入 11-20：无额外限制。 题目致谢：Aryansh Shrivastava, Benjamin Qi

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum