레이팅 미적용농부 존의 \(N\)마리 소들(\(2\le N\le 2\cdot 10^5\))은 \(1\dots N\)의 번호가 매겨져 있고, 처음에 \(N-1\)쌍의 친구 관계가 있어 트리를 이룬다. 소들은 한 마리씩 휴가를 떠나 농장을 떠난다. \(i\)일째에 \(i\)번째 소가 농장을 떠나고, 그 후 농장에 아직 남아 있는 \(i\)번째 소의 친구들의 모든 쌍이 서로 친구가 된다.
\(1\)부터 \(N\)까지의 각 \(i\)에 대해, \(i\)번째 소가 떠나기 직전에, \(a,b,c\) 중 누구도 휴가 중이 아니고, \(a\)와 \(b\)가 친구이며, \(b\)와 \(c\)가 친구인 서로 다른 소들의 순서쌍 \((a,b,c)\)는 몇 개인가?
출제자: Aryansh Shrivastava, Benjamin Qi
배점
- 입력 4-5: \(N\le 500\)
- 입력 6-10: \(N\le 5000\)
- 입력 11-20: 추가 제약 조건이 없다.
출제자: Aryansh Shrivastava, Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 \(N-1\)개의 줄에는 두 정수 \(u_i\)와 \(v_i\)가 주어지며, 이는 소 \(u_i\)와 \(v_i\)가 처음에 친구임을 나타낸다 (\(1\le u_i,v_i\le N\)).
\(1\)부터 \(N\)까지의 각 \(i\)에 대한 답을 각 줄에 출력한다.
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