통신망 지연
골드 I의견: 0
어느 나라에는 \(N\)개의 통신 중계소가 있고, 이들은 \(N-1\)개의 양방향 광케이블로 연결되어 전체가 하나의 트리를 이룬다. \(i\)번째 케이블은 두 중계소를 잇고, 신호가 그 케이블을 지나는 데 \(w\)만큼의 지연이 생긴다.
두 중계소 \(a\), \(b\) 사이에서 신호는 트리 위의 유일한 경로를 따라 전달된다. \(Q\)개의 질의가 주어질 때, 각 질의 \((a, b)\)에 대해 두 중계소 사이의 총 지연(경로 위 모든 케이블 지연의 합)을 구하여라.
중계소는 \(1\)번부터 \(N\)번까지 번호가 매겨져 있다.
\(1 \le N, Q \le 100\,000\)
\(1 \le u, v, a, b \le N\)
\(1 \le w \le 10^9\)
입력으로 주어지는 그래프는 항상 트리이다.
첫째 줄에 중계소의 개수 \(N\)이 주어진다.
다음 \(N-1\)개의 줄에 각각 세 정수 \(u\), \(v\), \(w\)가 주어진다. 이는 중계소 \(u\)와 \(v\)를 잇는 지연 \(w\)짜리 케이블을 의미한다.
그 다음 줄에 질의의 개수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각각 두 정수 \(a\), \(b\)가 주어진다.
각 질의에 대해 두 중계소 사이의 총 지연을 한 줄에 하나씩 출력한다. (단, \(a = b\)이면 \(0\)이다.)
5
1 2 3
1 3 5
3 4 2
3 5 4
3
2 4
4 5
2 210
6
0\(2 \to 1 \to 3 \to 4\) 경로 지연은 \(3+5+2=10\). \(4 \to 3 \to 5\)는 \(2+4=6\). \(2\)와 \(2\)는 같은 정점이라 \(0\).
2
1 2 7
2
1 2
2 17
7중계소가 둘뿐이며 둘 사이 지연은 \(7\). 방향은 무관하다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
통신망 지연
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
통신망 지연