숲 속의 전령
골드 III의견: 0
\(N\)개의 도시가 트리로 연결되어 있다 (루트 \(1\)). 각 간선에는 이동 거리(가중치)가 있다.
전령은 \(Q\)번의 임무를 수행한다. 각 임무에서 도시 \(u\)에서 도시 \(v\)까지 트리 위의 유일한 경로를 따라 이동할 때, 경로 위 간선의 가중치 합을 구하여라.
- \(1 \le N \le 200\,000\)
- \(1 \le Q \le 200\,000\)
- \(1 \le w \le 10^9\)
- \(1 \le u, v \le N\)
첫째 줄에 도시의 수 \(N\)과 쿼리의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(N-1\)개의 줄에 간선 \(u\) \(v\) \(w\)가 주어진다 (\(w\)는 가중치).
다음 \(Q\)개의 줄에 쿼리 \(u\) \(v\)가 주어진다.
\(Q\)개의 줄에 걸쳐 각 쿼리의 경로 가중치 합을 출력한다.
5 3
1 2 4
1 3 7
2 4 3
2 5 2
4 3
4 5
3 5
14
5
13
경로 \(4 \to 3\): \(4 \to 2 \to 1 \to 3\), 가중치 합 \(3+4+7=14\). 경로 \(4 \to 5\): \(4 \to 2 \to 5\), 합 \(3+2=5\). 경로 \(3 \to 5\): \(3 \to 1 \to 2 \to 5\), 합 \(7+4+2=13\).
5 3
1 2 1
2 3 2
3 4 3
4 5 4
1 5
2 4
3 3
10
5
0
체인 \(1\)-\(2\)-\(3\)-\(4\)-\(5\) (가중치 \(1,2,3,4\)). 경로 \(1 \to 5\): \(1+2+3+4=10\). 경로 \(2 \to 4\): \(2+3=5\). 경로 \(3 \to 3\): 같은 도시이므로 \(0\).
riseoj 작성
출처 Original
평가 및 의견
숲 속의 전령
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
숲 속의 전령