18376번 - 트리와 K번째 지름

오늘 알고리즘 과목의 중간고사가 있는 메시는 시험장에 들어서자마자 감독관에게 가중치 없는 트리를 받았다. 각각의 정점은 거리 1의 간선으로 연결되어 있으며, 임의의 두 정점 사이의 최단 경로가 유일하게 존재한다. i번 정점에 쓰여있는 정수를 J_i라고 할 때, J_i = i이다. 곧이어 들어온 이메이미 교수가 칠판에 다음과 같은 시험 문제를 적기 시작했다.

"트리의 s번 정점에서 출발하여 e번 정점에 도착하는 최단 경로를 10⁹ × J_s + J_e라는 수로 인코딩할 때, 주어진 트리에서 가장 긴 최단경로 (트리의 지름) 중 인코딩된 수가 K번째로 작은 것을 구하여라. 단, 인코딩된 수가 다르면 다른 지름으로 취급한다"

메시는 문제를 여기까지만 듣고 트리의 모든 지름을 O(N²)의 시간복잡도에 구하는 알고리즘을 짰다. 트리의 정점 수가 좀 많았지만 시험 시간은 48시간이기 때문에 아무런 문제가 되지 않았다. 메시는 지루한 기분을 달래기 위해 테트리스를 하기 시작했다.

하지만 이메이미 교수의 시험이 호락호락할 리가 없다! 이메이미 교수는 메시가 테트리스를 켠 것을 확인한 뒤 학생들의 화면에 queries.txt를 전송하고는 다음과 같이 말했다.

"설마 위 문제를 해결하지 못한 학생은 없겠죠? queries.txt에는 Q줄에 걸쳐 쿼리 u v L이 주어집니다. 각 쿼리마다 J_u와 J_v를 서로 바꾼 뒤 마찬가지로 인코딩한 수가 L번째로 작은 지름을 구하세요."

메시는 황급히 테트리스를 끄고 문제를 해결하려고 했지만 머릿속에 기록 경신을 코앞에 둔 테트리스만 생각나 집중할 수가 없었다. 메시가 이 수업을 드랍하지 않게 하기 위해 이 문제를 대신 해결해 주자.

1번째 줄에는 트리의 정점 수 N, 쿼리의 수 Q가 공백으로 구분되어 주어진다.

2번째 줄부터 N - 1개의 줄에 걸쳐 트리의 간선이 연결하는 두 정점의 번호 a, b가 공백으로 구분되어 주어진다.

N + 1번째 줄에는 K가 주어진다. 이는 처음 주어진 트리에서 K번째로 작은 지름을 구해야 한다는 것을 의미한다.

N + 2번째 줄부터 Q개의 줄에 걸쳐 쿼리 u, v, L이 공백으로 구분되어 주어진다. 이는 J_u와 J_v를 바꾼 뒤 L번째로 작은 지름을 구해야 한다는 것을 의미한다.

지름을 구하라는 쿼리가 들어올 때마다 지름을 인코딩한 수를 한 줄에 하나씩 출력한다. 조건을 만족하는 지름이 존재하지 않을 경우 -1을 출력한다.

• 2 ≤ N ≤ 250,000
• 0 ≤ Q ≤ 250,000
• 1 ≤ K ≤ 10¹⁸
• 모든 쿼리에서 1 ≤ u, v ≤ N, 1 ≤ L ≤ 10¹⁸