| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 9 | 6 | 6 | 66.667% |
병우는 나뭇잎 마을의 이장이다. 나뭇잎 마을은 $N$개의 시장과 두 시장을 잇는 $N-1$개의 거리 1ドル$의 양방향 도로로 이루어져 있다. 임의의 서로 다른 두 시장을 도로만을 이용하여 오갈 수 있다. 즉, 나뭇잎 마을은 트리 모양이다. 편의상 각 시장에 1ドル$부터 $N$까지 번호를 매겨 표현하자.
최근 나뭇잎 마을은 경제 활성화로 인해 시장과 시장 사이에 물건을 옮길 필요가 많아지고 있다. 이러한 요청은 총 $Q$개로, 각 요청을 $(a, b, w)$ 라는 정수들로 표현할 수 있다. 이는 $a$번 시장에서 $b$번 시장까지 총 $w$ kg의 물건을 옮겨달라는 요청이다. 병우는 요청들을 해결하기 위해 닌자들을 고용했다. 닌자 택배를 효율적으로 활용하기 위해서는 물류 허브로 사용할 두 시장 $x$와 $y$를 잘 골라야 한다. $x$와 $y$가 서로 다를 필요는 없다.
두 시장 $a, b$에 대해, $d(a, b)$를 $a$에서 $b$로 도로만을 이용하여 갈 수 있는 최단 거리로 정의하자.
즉, $a$번 시장에서 $b$번 시장으로 $w$ kg의 물건을 옮기기 위해서는 $w(s_{a}d(a, x) + u d(x, y) + t_{b}d(y, b))$의 비용이 필요함을 알 수 있다. 시장 $x, y$를 적절히 골라, 모든 $Q$개의 요청에 대한 비용의 합을 최소화하는 프로그램을 작성하여라.
첫째 줄에 나뭇잎 마을에 존재하는 시장의 개수 $N$이 주어진다.
둘째 줄부터 $N-1$개의 줄에 걸쳐 트리의 간선에 해당하는 도로에 대한 정보가 주어진다. $i+1$번째 줄에는 두 정수 $u$ $v$가 공백을 사이에 두고 주어지며, 이는 $i+1$번째 도로가 $u$번 시장과 $v$번 시장을 잇는다는 뜻이다. 1ドル \le u \neq v \le N$이며, 나뭇잎 마을은 트리 모양임이 보장된다.
$N+1$번째 줄부터 $N$개의 줄에 걸쳐 두 정수 $s_{i}, t_{i}$가 공백을 사이에 두고 주어진다. $s_{i}$는 $i$번 시장에서 $x$번 시장까지 1kg의 물건을 옮기는 데 드는 단위 거리당 비용, $t_{i}$는 $y$번 시장에서 $i$번 시장까지 1kg의 물건을 옮기는 데 드는 단위 거리당 비용을 나타낸다.
2ドルN+1$번째 줄에는 물건 수송 요청의 개수 $Q$가 주어진다.
2ドルN+2$번째 줄부터 $Q$개의 줄에 걸쳐 세 정수 $a, b, w$가 공백을 사이에 두고 주어진다. 이는 $a$번 시장에서 $b$번 시장까지 $w$kg의 물건을 옮겨달라는 요청이 있음을 의미한다. $a, b$는 서로 같을 수 있고, 동일한 $(a, b)$에 대해 여러 요청이 주어질 수 있음에 주의하자.
마지막 줄에는 $x$번 시장에서 $y$번 시장까지 1kg의 물건을 옮기기 위한 단위 거리당 비용 $u$가 주어진다.
첫째 줄에 $Q$개의 요청에 대한 비용의 합으로 가능한 최솟값을 출력한다.
1ドル \le N, Q \le 500$.
1ドル \le N, Q \le 2,000円$.
$u = 0$.
추가 제한 조건이 없다.
6 4 2 2 1 2 5 1 6 2 3 9 7 10 1 2 2 3 6 10 9 4 10 8 6 6 6 5 4 5 6 2 1 4 5 4 4 5 4 5 2 9 2 2 6 3 3 10 4
482