문제
옛날 옛적 N개의 도시로 이루어진 한 나라가 있었다.
도시들은 도로로 연결되었으며 트리 구조를 이루었으며 1번 도시가 나라의 수도였다.
각 도시에는 전령들이 있어 도시에 긴급한 일이 생기면 이들이 수도로 메시지를 전달하는 역할을 한다.
메시지의 전달 방식은 다음과 같다.
우선 메시지가 출발하는 도시의 전령은 무조건 수도 방향으로 이동한다.
그러다가, 다른 도시에 도달하면 그 도시의 전령에게 메시지를 넘겨줄 수 있고 메시지를 받은 전령은 같은 방식으로 전달을 한다.
도시에 도착했다고 해서 무조건 메시지를 넘겨줄 필요는 없으며 한 명의 전령이 끝까지 메시지를 옮겨도 된다.
i번 도시의 전령이 움직이는 데는 출발 전의 준비에 S_i 분, 이동 시 1km당 V_i 분이 걸린다.
우리의 목적은 각 도시마다 해당 도시에서 출발해 수도로 메시지를 전달하는 최소시간을 계산하는 것이다.
입력
첫 줄에 N이 주어진다. (3 <= N <= 100000)
다음 줄부터 N-1개의 줄에 줄마다 세 정수 u, v, d가 주어진다. (1 <= d <= 10000)
이는 u와 v사이에 거리 d km의 도로가 존재한다는 뜻이다.
다음 N-1줄에는 2번 도시부터 N번 도시까지 각 도시의 전령의 S_i, V_i가 주어진다. (0 <= S_i <= 10^9, 1 <= V_i <= 10^9)
출력
한 줄에 2번 도시부터 N번 도시까지 각 도시에서 메시지를 전달하기 시작할 때 수도에 도달하는 데 걸리는 최소 시간을 공백으로 구분해 출력하라.
예제
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
206 321 542 328
출처
CEOI 2009
로그인해야 코드를 작성할 수 있어요.