경로 위의 k번째 정점
플래티넘 V의견: 0
\(N\)개의 정점으로 이루어진 트리가 주어진다. 트리에서 서로 다른 두 정점 사이에는 유일한 경로가 있다.
\(Q\)개의 질의가 주어진다. 각 질의는 세 정수 \(u\), \(v\), \(k\)로 이루어진다. \(u\)에서 \(v\)로 가는 경로 위의 정점들을 \(u\)부터 차례로 나열했을 때, \(k\)번째 정점(\(u\) 자신이 \(1\)번째)의 번호를 출력해야 한다. 경로 위의 정점이 \(k\)개보다 적으면 \(-1\)을 출력한다. \(u=v\)인 경우 경로는 정점 하나로만 이루어진다.
\(1 \le N \le 100\,000\), \(1 \le Q \le 100\,000\), \(1 \le k \le N\).
첫째 줄에 정점의 개수 \(N\)이 주어진다. 다음 \(N-1\)개의 줄에 간선의 정보 \(a\ b\)가 주어진다 — 정점 \(a\)와 \(b\)를 잇는 간선이다. 그다음 줄에 질의의 개수 \(Q\)가 주어지고, 이어지는 \(Q\)개의 줄에 각각 세 정수 \(u\ v\ k\)가 주어진다.
각 질의마다 한 줄에 경로 위의 \(k\)번째 정점의 번호를, 그런 정점이 없으면 \(-1\)을 출력한다.
6
1 2
2 3
3 4
2 5
3 6
9
1 4 1
1 4 2
1 4 4
1 4 5
5 6 1
5 6 3
5 6 4
3 3 1
3 3 2
1
2
4
-1
5
3
6
3
-1
\(1\!\to\!4\) 경로는 \(1,2,3,4\)이므로 \(1\)번째는 \(1\), \(2\)번째는 \(2\), \(4\)번째는 \(4\), \(5\)번째 정점은 없어 \(-1\)이다.
2
1 2
5
1 2 1
1 2 2
1 2 3
2 1 1
1 1 1
1
2
-1
2
1
\(1\!\to\!2\) 경로는 두 정점뿐이라 \(3\)번째는 \(-1\), 방향을 바꾸면 첫 정점은 \(2\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
경로 위의 k번째 정점
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
경로 위의 k번째 정점