Triples of Cows
다이아몬드 I의견: 0
There are initially \(N-1\) pairs of friends among FJ's \(N\)
(\(2\le N\le 2\cdot 10^5\)) cows labeled \(1\dots N\), forming a tree. The cows are
leaving the farm for vacation one by one. On day \(i\), the \(i\)th cow leaves the
farm, and then all pairs of the \(i\)th cow's friends still present on the farm
become friends.
For each \(i\) from \(1\) to \(N\), just before the \(i\)th cow leaves, how many
ordered triples of distinct cows \((a,b,c)\) are there such that none of \(a,b,c\)
are on vacation, \(a\) is friends with \(b\), and \(b\) is friends with \(c\)?
Problem credits: Aryansh Shrivastava, Benjamin Qi
SCORING
- Inputs 4-5: \(N\le 500\)
- Inputs 6-10: \(N\le 5000\)
- Inputs 11-20: No additional constraints.
Problem credits: Aryansh Shrivastava, Benjamin Qi
The first line contains \(N\).
The next \(N-1\) lines contain two integers \(u_i\) and \(v_i\) denoting that cows
\(u_i\) and \(v_i\) are initially friends (\(1\le u_i,v_i\le N\)).
The answers for \(i\) from \(1\) to \(N\) on separate lines.
3
1 2
2 32
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.
4
1 2
1 3
1 46
6
0
0At 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.
5
3 5
5 1
1 4
1 28
10
2
0
0riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > US Open > Platinum
평가 및 의견
Triples of Cows
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Triples of Cows