황금 중간 지점
골드 I의견: 0
\(N\)개의 도시가 트리로 연결되어 있다 (루트 \(1\)). 탐험가는 \(Q\)번의 임무를 수행한다. 각 임무는 출발 도시 \(u\), 도착 도시 \(v\), 정수 \(K\)로 이루어지며, \(u\)에서 \(v\)까지의 경로(\(u\)를 \(1\)번째 노드로 셈)에서 \(K\)번째 노드를 구하는 것이다.
공식적으로, \(u\)에서 \(v\)로 가는 유일한 단순 경로를 \(p_1 = u, p_2, \dots, p_L = v\) 로 나열할 때, \(p_K\)를 구하여라.
- \(1 \le N \le 200\,000\)
- \(1 \le Q \le 200\,000\)
- \(1 \le u, v \le N\)
- \(1 \le K \le\) (경로 위의 노드 수)
첫째 줄에 도시의 수 \(N\)과 쿼리의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(N-1\)개의 줄에 간선 \(u\) \(v\)가 주어진다.
다음 \(Q\)개의 줄에 쿼리 \(u\) \(v\) \(K\)가 주어진다 (\(1 \le K \le \text{경로의 노드 수}\)).
\(Q\)개의 줄에 걸쳐 각 쿼리의 \(K\)번째 노드를 출력한다.
5 5
1 2
1 3
2 4
2 5
4 3 1
4 3 2
4 3 3
4 5 2
3 3 1
4
2
1
2
3
경로 \(4 \to 3\): \([4, 2, 1, 3]\) (총 \(4\)개 노드). \(K=1\)이면 \(4\), \(K=2\)이면 \(2\), \(K=3\)이면 \(1\). 경로 \(4 \to 5\): \([4, 2, 5]\), \(K=2\)이면 \(2\). 경로 \(3 \to 3\): \([3]\), \(K=1\)이면 \(3\).
5 4
1 2
2 3
3 4
4 5
1 5 1
1 5 3
1 5 5
5 1 2
1
3
5
4
체인 \(1\)-\(2\)-\(3\)-\(4\)-\(5\). 경로 \(1 \to 5\): \([1,2,3,4,5]\), \(K=1\)이면 \(1\), \(K=3\)이면 \(3\), \(K=5\)이면 \(5\). 경로 \(5 \to 1\) (역방향): \([5,4,3,2,1]\), \(K=2\)이면 \(4\).
riseoj 작성
출처 Original
평가 및 의견
황금 중간 지점
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
황금 중간 지점