트리에서의 거리
골드 II의견: 0
\(N\)개의 정점으로 이루어진 가중치 트리가 주어진다. 트리에서 서로 다른 두 정점 사이에는 유일한 경로가 있다.
\(Q\)개의 질의가 주어진다. 각 질의는 두 정점 \(u\), \(v\)로 이루어지며, \(u\)에서 \(v\)까지 경로에 놓인 간선들의 가중치 합, 즉 두 정점 사이의 거리를 출력해야 한다. \(u=v\)이면 거리는 \(0\)이다.
\(1 \le N \le 100\,000\), \(1 \le Q \le 100\,000\), \(1 \le w \le 10^9\). 답은 64비트 정수 범위 안에 들어간다.
첫째 줄에 정점의 개수 \(N\)이 주어진다. 다음 \(N-1\)개의 줄에 간선의 정보 \(a\ b\ w\)가 주어진다 — 정점 \(a\)와 \(b\)를 잇는 가중치 \(w\)의 간선이다. 그다음 줄에 질의의 개수 \(Q\)가 주어지고, 이어지는 \(Q\)개의 줄에 각각 두 정점 \(u\ v\)가 주어진다.
각 질의마다 한 줄에 두 정점 사이의 거리를 출력한다.
5
1 2 3
1 3 5
3 4 2
3 5 7
4
2 4
4 5
1 1
2 5
10
9
0
15
\(2\)에서 \(4\)까지는 \(2\!-\!1\!-\!3\!-\!4\) 경로로 \(3+5+2=10\)이다.
2
1 2 1000000000
3
1 2
2 1
1 1
1000000000
1000000000
0
간선이 하나뿐이면 두 끝 정점 사이 거리는 그 가중치이다.
골드 III
골드 I
플래티넘 V막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
트리에서의 거리
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
트리에서의 거리