광케이블 최대 지연
골드 I의견: 0
\(N\)개의 도시가 광케이블로 연결되어 트리를 이룬다. 각 케이블에는 지연시간(가중치)이 있다.
\(Q\)개의 질의가 주어지며, 각 질의는 두 도시 \(a, b\)를 잇는 (유일한) 경로 위에 있는 케이블들의 지연시간 중 최댓값을 묻는다. \(a=b\)이면 경로에 케이블이 없으므로 답은 \(0\)이다.
모든 질의에 대한 답을 출력하라.
\(1 \le N \le 100{,}000\), \(1 \le Q \le 100{,}000\), \(1 \le w \le 10^9\), \(1 \le u,v,a,b \le N\). 입력 그래프는 항상 트리이다.
첫째 줄에 도시의 수 \(N\). 다음 \(N-1\)개의 줄에 \(u\;v\;w\) (도시 \(u\)와 \(v\)를 잇는 지연시간 \(w\)의 케이블). 그 다음 줄에 질의 수 \(Q\). 이후 \(Q\)개의 줄에 \(a\;b\)가 주어진다. 도시는 \(1\)번부터 번호가 매겨진다.
각 질의마다 한 줄에 경로 위 최대 지연시간을 출력한다.
5
1 2 4
1 3 7
3 4 2
3 5 9
3
2 4
4 5
2 2
7
9
0\(2\to4\) 경로의 간선 가중치는 \(4,7,2\)이고 최댓값 \(7\). \(4\to5\)는 \(2,9\)로 \(9\). \(2\to2\)는 자기 자신이라 간선이 없어 \(0\).
4
1 2 5
2 3 3
3 4 8
2
1 4
1 3
8
5직선 트리에서 \(1\to4\)의 간선은 \(5,3,8\)이고 최댓값 \(8\). \(1\to3\)은 \(5,3\)으로 \(5\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
광케이블 최대 지연
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
광케이블 최대 지연