시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (추가 시간 없음) 1024 MB 130 19 13 11.017%

문제

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

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

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

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

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

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

입력

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

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

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

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

출력

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

제한

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

예제 입력 1

4 1
1 2
1 3
1 4
1
1 2 1

예제 출력 1

2000000003
1000000003

예제 입력 2

10 5
9 7
6 7
1 7
10 9
4 9
2 9
5 6
3 1
8 1
4
3 2 9
3 9 5
2 10 23
3 2 22
9 1 3

예제 출력 2

3000000002
4000000005
4000000008
-1
10000000009
3000000010

출처

Contest > IDTcup > 제 2회 IDTcup D번

  • 문제를 만든 사람: TAMREF