D. 트리와 K번째 지름 | imeimi PS archive

문제

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

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

메시는 문제를 여기까지만 듣고 트리의 모든 지름을 $O(N^{2})$ 의 시간복잡도에 구하는 알고리즘을 짰다. 트리의 정점 수가 좀 많았지만 시험 시간은 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^{18}$
모든 쿼리에서 1 ≤ u, v ≤ N, 1 ≤ L ≤ $10^{18}$

2000000003
1000000003

3000000002
4000000005
4000000008
-1
10000000009
3000000010

출처

문제를 만든 사람: TAMREF