배달 로봇의 경로
실버 III의견: 0
스마트 물류 센터의 \(N\)개 창고는 \(N-1\)개의 통로로 연결되어 있으며 트리 구조를 이룬다. 각 통로에는 이동 시간(양의 정수, 초)이 부여되어 있다.
배달 로봇은 두 창고 사이를 반드시 트리 상의 유일한 경로를 통해 이동한다. 운영팀은 \(Q\)개의 쿼리를 처리해야 한다. 각 쿼리는 두 창고 번호 \(u\), \(v\)로 이루어지며, 다음 두 값을 출력해야 한다:
- \(u\)에서 \(v\)까지의 경로에 있는 통로의 이동 시간 합
- \(u\)에서 \(v\)까지 지나는 통로의 수
같은 창고를 출발·도착지로 지정하면 이동 시간은 \(0\)이고 통로 수도 \(0\)이다.
- \(1 \le N \le 2\,000\)
- \(1 \le Q \le 2\,000\)
- \(1 \le w \le 10^6\)
첫째 줄에 창고의 수 \(N\)과 쿼리의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(N-1\)개의 줄에 통로로 연결된 두 창고 번호 \(u\), \(v\)와 이동 시간 \(w\)가 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 쿼리 창고 번호 \(u\), \(v\)가 공백으로 구분되어 주어진다.
\(Q\)개의 줄에 걸쳐 각 쿼리의 이동 시간 합과 통로 수를 공백으로 구분해 출력한다.
5 2
1 2 3
1 3 5
2 4 2
2 5 7
3 4
4 5
10 3
9 2
\(3\to4\) 경로는 \(3\!\to\!1\!\to\!2\!\to\!4\)이고 가중치 합 \(5+3+2=10\), 간선 수 \(3\)이다. \(4\to5\) 경로는 \(4\!\to\!2\!\to\!5\)이고 가중치 합 \(2+7=9\), 간선 수 \(2\)이다.
4 2
1 2 1
2 3 4
3 4 2
1 4
2 3
7 3
4 1
\(1\to4\) 경로는 \(1\!\to\!2\!\to\!3\!\to\!4\)이고 가중치 합 \(1+4+2=7\), 간선 수 \(3\)이다. \(2\to3\) 경로는 단일 간선이므로 가중치 \(4\), 간선 수 \(1\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
배달 로봇의 경로
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
배달 로봇의 경로