DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

I need ㅠ

문제로 돌아가기

해설

함수 그래프와 구성 각 정점에서 i→Pii\to P_ii→Pi​를 그리면 모든 정점의 진출 차수가 111인 함수 그래프가 된다. 각 약한 연결 컴포넌트에는 방향 사이클이 정확히 하나 있고, 나머지 간선은 그 사이클로 향하는 트리들을 이룬다.

길이 333 이상의 사이클에서는 간선 하나를 제외하고 나머지를 친구 관계로 만든다. 길이 222의 사이클은 같은 두 정점 사이의 양방향 선호이므로 친구 관계 하나만 만든다. 자기 루프는 만들지 않는다. 사이클 바깥의 간선은 모두 유지한다. 이렇게 얻은 포레스트의 컴포넌트들을 임의의 간선으로 연결하면 트리가 된다.

DSU를 사용하면 사이클을 별도로 찾지 않고도 구성할 수 있다. 모든 (i,Pi)(i,P_i)(i,Pi​)에 대해 두 정점이 다른 집합에 있을 때만 간선을 추가하고 합친다. 마지막으로 정점 111과 아직 다른 집합에 있는 정점을 연결한다.

최솟값의 증명 Pi=iP_i=iPi​=i인 항은 항상 000이고, 사이클 밖의 Pi≠iP_i\neq iPi​인 항은 적어도 이다. 길이 인 방향 사이클을 생각하자. 임의의 최종 트리에서 사이클의 정점들을 순서대로 방문하고 처음으로 돌아오는 경로를 이어 붙인다. 사이클 정점들을 연결하는 최소 부분 트리의 모든 간선은 이 닫힌 이동에서 적어도 두 번 지나간다. 그 부분 트리는 서로 다른 개 정점을 포함하므로 간선이 적어도 개이다. 따라서 이 사이클에 해당하는 거리 합은 적어도 이다. 다른 컴포넌트의 정점을 경유하더라도 이 하한은 변하지 않는다.

위 구성에서 길이 L≥3L\geq3L≥3인 사이클은 L−1L-1L−1개의 관계가 거리 111이고, 제외한 관계의 거리는 L−1L-1L−1이므로 합이 정확히 2(L−이다. 길이 이면 두 선호의 거리가 모두 이다. 사이클 밖의 선호도 모두 거리 이다. 컴포넌트를 잇는 간선은 기존 컴포넌트 내부의 유일한 경로를 바꾸지 않는다. 따라서 모든 하한을 동시에 달성한다.

최솟값은 다음과 같다.

OPT=#{i:Pi≠i}+∑directed cycles Cmax⁡(0,∣C∣−2).\mathrm{OPT}=\#\{i:P_i\neq i\}+\sum_{\text{directed cycles }C}\max(0,|C|-2).OPT=#{i:Pi​

진입 차수가 000인 정점들을 큐로 제거하면 사이클 정점만 남는다. 남은 사이클들을 순회하여 길이를 세면 위 값을 O(N)O(N)O(N)에 계산할 수 있다. 서로를 가리키는 두 사람은 친구 관계 하나를 공유하지만 목적함수에서는 두 항을 각각 센다는 점에 주의한다.

복잡도와 검증 정답 구성은 O(Nα(N))O(N\alpha(N))O(Nα(N)) 시간과 O(N)O(N)O(N) 공간을 사용한다. 깊이가 NNN인 그래프도 가능하므로 참조 구현은 재귀 DFS를 사용하지 않는다. 최솟값은 000 이상 2N−22N-2 이하이다. 잘못된 후보 트리의 거리 합은 최대 이므로 체커의 거리 합은 64비트로 계산한다. 그 밖의 정점 번호, 차수, 깊이는 이하이다.

체커는 출력 간선의 개수, 정점 범위와 트리 여부를 검사하고, LCA로 실제 거리 합을 계산하여 독립적으로 구한 최솟값과 비교한다. 체커의 시간과 공간은 O(Nlog⁡N)O(N\log N)O(NlogN)이다.

서브태스크 1은 모든 프뤼퍼 수열을 열거하여 NN−2N^{N-2}NN−2개의 라벨 트리를 검사한다. 각 트리에서 모든 시작점의 BFS로 목적함수를 계산하므로 시간은 O(NN−2N2)O(N^{N-2}N^2)O(NN−2N2, 공간은 이하이다. 에서 충분하다. 서브태스크 4는 함수 그래프와 DSU를 사용한다.

Solution written by GPT6

=
i
111
L≥2L\geq2L≥2
LLL
L−1L-1L−1
2(L−1)2(L-1)2(L−1)
1)2(L-1)
2(L−1)
222
111
111
=
i}+
directed cycles C∑​max(0,∣C∣−
2).
2N−
2
N(N−1)<2.5⋅1011N(N-1)<2.5\cdot10^{11}N(N−1)<2.5⋅1011
NNN
)
O(N2)O(N^2)O(N2)
N≤7N\leq7N≤7