#PU1334. USACO 2023 US Open Contest, Platinum — Problem 3. Triples of Cows
USACO 2023 US Open Contest, Platinum — Problem 3. Triples of Cows
USACO 2023 US Open Contest, Platinum — Problem 3. Triples of Cows
题目描述
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.
数据范围
Inputs 4-5: Inputs 6-10: Inputs 11-20: No additional constraints. Problem credits: Aryansh Shrivastava, Benjamin Qi
样例
样例 1
3
1 2
2 3
2
0
0
$(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.
样例 2
4
1 2
1 3
1 4
6
6
0
0
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.
样例 3
5
3 5
5 1
1 4
1 2
8
10
2
0
0