경로의 최대 간선
플래티넘 V의견: 0
\(N\)개의 정점으로 이루어진 가중치 트리가 주어진다. 트리에서 서로 다른 두 정점 사이에는 유일한 경로가 존재한다.
각 질의 \(u\ v\)에 대해, 정점 \(u\)에서 정점 \(v\)로 가는 경로 위에 있는 간선들 중 가중치가 가장 큰 간선의 가중치를 출력하여라. 모든 질의에서 \(u \ne v\)가 보장되므로 경로 위에는 적어도 하나의 간선이 존재한다.
\(2 \le N \le 100\,000\), \(1 \le Q \le 100\,000\), \(1 \le a, b, u, v \le N\), \(u \ne v\), \(1 \le w \le 10^9\).
첫째 줄에 정점의 개수 \(N\)이 주어진다. 다음 \(N-1\)개의 줄에 간선의 정보 \(a\ b\ w\)가 주어진다 — 정점 \(a\)와 \(b\)를 잇는 가중치 \(w\)의 간선이다.
그 다음 줄에 질의의 개수 \(Q\)가 주어지고, 이어지는 \(Q\)개의 줄에 각 질의 \(u\ v\)가 주어진다 (\(u \ne v\)).
각 질의마다 한 줄에, \(u\)에서 \(v\)로 가는 경로 위 간선 중 최대 가중치를 출력한다.
5
1 2 6
2 3 5
2 4 3
1 5 10
3
3 5
4 3
5 4
10
5
10
\(3\to5\) 경로의 간선은 \(5,6,10\)이라 최댓값 \(10\). \(4\to3\)은 \(3,5\)라 \(5\). \(5\to4\)는 \(10,6,3\)이라 \(10\).
2
1 2 7
2
1 2
2 1
7
7
간선이 하나뿐이라 두 질의 모두 \(7\)이다.
골드 II
골드 I막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
경로의 최대 간선
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
경로의 최대 간선