#P9194. [USACO23OPEN] Triples of Cows P
[USACO23OPEN] Triples of Cows P
题目描述
There are initially pairs of friends among FJ's cows labeled , forming a tree. The cows are leaving the farm for vacation one by one. On day , the th cow leaves the farm, and then all pairs of the th cow's friends still present on the farm become friends.
For each from to , just before the th cow leaves, how many ordered triples of distinct cows are there such that none of are on vacation, is friends with , and is friends with ?
输入格式
The first line contains .
The next lines contain two integers and denoting that cows and are initially friends.
输出格式
The answers for from to on separate lines.
题目大意
题目描述
最初,农夫 John 的 头编号为 的奶牛中有 对朋友关系,形成一棵树。奶牛们依次离开农场去度假。在第 天,第 头奶牛离开农场,然后所有仍在农场中的第 头奶牛的朋友之间会成为朋友。
对于每个 从 到 ,在第 头奶牛离开之前,有多少个有序三元组 满足以下条件: 均未离开农场, 与 是朋友,且 与 是朋友?
输入格式
第一行包含 。
接下来的 行,每行包含两个整数 和 ,表示奶牛 和 最初是朋友。
输出格式
输出 行,第 行表示在第 头奶牛离开之前的答案。
提示
对于第一个样例:
- 在第 头奶牛离开之前,三元组为 和 。
- 在第 头奶牛离开后,剩下的奶牛少于 头,因此没有三元组。
对于第二个样例:
- 最初,奶牛 与所有其他奶牛是朋友,而其他奶牛之间没有朋友关系,因此三元组为 ,其中 是 中的不同奶牛,共有 个三元组。
- 在第 头奶牛离开后,剩下的三头奶牛彼此都是朋友,因此三元组为这三头奶牛的任意排列,共有 个三元组。
- 在第 头奶牛离开后,剩下的奶牛少于 头,因此没有三元组。
,。
- 输入 4-5:。
- 输入 6-10:。
- 输入 11-20:没有额外限制。
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
提示
For the first sample:
and are the triples just before cow leaves.
After cow
leaves, there are less than cows left, so no triples are possible.
For the second sample:
At the beginning, cow is friends with all other cows, and no other pairs of
cows are friends, so the triples are where are different cows
from , which gives triples.
After cow leaves, the remaining three cows are all friends, so the triples
are just those three cows in any of the possible orders.
After cow leaves, there are less than cows left, so no triples are
possible.
, .
- Inputs 4-5: .
- Inputs 6-10: .
- Inputs 11-20: No additional constraints.