6167 : K번째 조상
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
트리의 각 노드 u와 정수 K가 쿼리로 주어질 때, u의 K번째 조상 노드 번호를 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N과 쿼리의 개수 Q (1 ≤ N, Q ≤ 100,000)가 주어집니다.
둘째 줄부터 N-1개의 줄에 간선 정보 u, v가 주어집니다.
그 다음 Q개의 줄에 쿼리 u, K가 주어집니다.
둘째 줄부터 N-1개의 줄에 간선 정보 u, v가 주어집니다.
그 다음 Q개의 줄에 쿼리 u, K가 주어집니다.
출력 설명
각 쿼리에 대해 K번째 조상의 번호를 출력합니다. 조상이 존재하지 않으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
1 2
2 3
3 4
4 5
5 2
3 3
4 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
-1
3