20132번 - Parity Constraint Minimum Spanning Tree

2019년에 연세대학교 최적화 연구실에서는 갑자기 특정 문제에 Parity Constraint(홀짝 제약)을 넣은 상태로 문제를 푸는 것이 유행한 적이 있었고, 졸업하신 김강산 선배도 Parity Constraint 관련 논문을 작성하셨다. 이를 기념하기 위해서 국렬이는 연세대학교 프로그래밍 경진대회에 Parity Constraint 문제를 내기로 하였다.

정점이 N개, 비용이 있는 무방향 간선이 M개 있는 그래프가 주어진다. 모든 정점에는 1부터 N까지 번호가 매겨져 있다. 임의의 정점을 선택했을 때 다른 정점으로 가는 경로는 항상 존재하며, 서로 다른 두 정점 사이에는 최대 한 개의 간선이 존재한다.

스패닝 트리는 주어진 그래프의 부분 그래프들 중 트리인 것을 의미한다. 스패닝 트리의 가능한 비용의 합 중 홀수인 최솟값, 짝수인 최솟값을 구하여라.

다음과 같이 입력이 주어진다.

스패닝 트리의 가능한 비용의 합 중 홀수인 최솟값, 짝수인 최솟값을 구하여라. 만약에 해당하는 트리가 존재하지 않는 경우 -1을 출력한다.

• 2 ≤ N ≤ 100,000.
• 1 ≤ M ≤ 300,000.
• 1 ≤ u_i, v_i ≤ N. u_i ≠ v_i. u_i와 v_i는 i번째 간선의 양 끝점을 의미한다.
• 1 ≤ w_i ≤ 1,000,000,000. w_i는 i번째 간선의 비용을 의미한다.
• 입력에 주어진 수들은 전부 정수다.