함수 그래프와 구성 각 정점에서 를 그리면 모든 정점의 진출 차수가 인 함수 그래프가 된다. 각 약한 연결 컴포넌트에는 방향 사이클이 정확히 하나 있고, 나머지 간선은 그 사이클로 향하는 트리들을 이룬다.
길이 이상의 사이클에서는 간선 하나를 제외하고 나머지를 친구 관계로 만든다. 길이 의 사이클은 같은 두 정점 사이의 양방향 선호이므로 친구 관계 하나만 만든다. 자기 루프는 만들지 않는다. 사이클 바깥의 간선은 모두 유지한다. 이렇게 얻은 포레스트의 컴포넌트들을 임의의 간선으로 연결하면 트리가 된다.
DSU를 사용하면 사이클을 별도로 찾지 않고도 구성할 수 있다. 모든 에 대해 두 정점이 다른 집합에 있을 때만 간선을 추가하고 합친다. 마지막으로 정점 과 아직 다른 집합에 있는 정점을 연결한다.
최솟값의 증명 인 항은 항상 이고, 사이클 밖의 인 항은 적어도 이다. 길이 인 방향 사이클을 생각하자. 임의의 최종 트리에서 사이클의 정점들을 순서대로 방문하고 처음으로 돌아오는 경로를 이어 붙인다. 사이클 정점들을 연결하는 최소 부분 트리의 모든 간선은 이 닫힌 이동에서 적어도 두 번 지나간다. 그 부분 트리는 서로 다른 개 정점을 포함하므로 간선이 적어도 개이다. 따라서 이 사이클에 해당하는 거리 합은 적어도 이다. 다른 컴포넌트의 정점을 경유하더라도 이 하한은 변하지 않는다.
위 구성에서 길이 인 사이클은 개의 관계가 거리 이고, 제외한 관계의 거리는 이므로 합이 정확히 이다. 길이 이면 두 선호의 거리가 모두 이다. 사이클 밖의 선호도 모두 거리 이다. 컴포넌트를 잇는 간선은 기존 컴포넌트 내부의 유일한 경로를 바꾸지 않는다. 따라서 모든 하한을 동시에 달성한다.
최솟값은 다음과 같다.
진입 차수가 인 정점들을 큐로 제거하면 사이클 정점만 남는다. 남은 사이클들을 순회하여 길이를 세면 위 값을 에 계산할 수 있다. 서로를 가리키는 두 사람은 친구 관계 하나를 공유하지만 목적함수에서는 두 항을 각각 센다는 점에 주의한다.
복잡도와 검증 정답 구성은 시간과 공간을 사용한다. 깊이가 인 그래프도 가능하므로 참조 구현은 재귀 DFS를 사용하지 않는다. 최솟값은 이상 이하이다. 잘못된 후보 트리의 거리 합은 최대 이므로 체커의 거리 합은 64비트로 계산한다. 그 밖의 정점 번호, 차수, 깊이는 이하이다.
체커는 출력 간선의 개수, 정점 범위와 트리 여부를 검사하고, LCA로 실제 거리 합을 계산하여 독립적으로 구한 최솟값과 비교한다. 체커의 시간과 공간은 이다.
서브태스크 1은 모든 프뤼퍼 수열을 열거하여 개의 라벨 트리를 검사한다. 각 트리에서 모든 시작점의 BFS로 목적함수를 계산하므로 시간은 , 공간은 이하이다. 에서 충분하다. 서브태스크 4는 함수 그래프와 DSU를 사용한다.
Solution written by GPT6