주차장 출구 위치 정하기

문제

한 주차장은 N개의 구역으로 이루어져 있고, 구역 사이를 잇는 N-1개의 통로가 있어 모든 구역이 서로 오갈 수 있다. 즉 구역과 통로는 트리를 이룬다. 각 통로에는 양방향으로 지나는 데 드는 거리가 정해져 있다. i번 구역에는 현재 c_i대의 차량이 주차되어 있다. 주차장 관리자는 새 출구를 구역 하나에 설치하려 한다. 출구를 x번 구역에 설치하면, 모든 차량이 자기 구역에서 x번 구역까지 통로를 따라 이동하므로 총 비용은 (각 구역 i에 대해 c_i와 i에서 x까지의 거리를 곱한 값)을 모든 구역에 대해 더한 값이다. 단, 구역마다 출구를 설치할 수 있는지 여부가 정해져 있다. f_i가 1이면 i번 구역에 설치할 수 있고, 0이면 설치할 수 없다. 설치할 수 있는 구역 중 총 비용이 가장 작은 구역을 찾으시오. 비용이 같은 구역이 여러 개이면 번호가 가장 작은 구역을 택한다. 설치할 수 있는 구역이 하나도 없으면 -1을 출력한다. 모든 값은 정수이다.

입력

첫 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 둘째 줄에 c_1, ..., c_N이 공백으로 구분되어 주어진다. (0 ≤ c_i ≤ 100) 셋째 줄에 f_1, ..., f_N이 공백으로 구분되어 주어진다. (f_i는 0 또는 1) 이어서 N-1개의 줄에 통로 정보 u, v, w가 공백으로 구분되어 주어진다. (1 ≤ u, v ≤ N, 1 ≤ w ≤ 100) u번 구역과 v번 구역을 거리 w인 통로가 잇는다는 뜻이다.

출력

설치할 구역이 있으면 선택한 구역 번호와 그 총 비용을 공백으로 구분하여 한 줄에 출력한다. 없으면 -1을 출력한다.

5
2 1 3 1 2
0 1 1 1 1
1 2 3
1 3 1
2 4 2
2 5 4

2 28

1
5
0

-1

2
0 0
1 1
1 2 7

1 0

출처: Devin.KR 자체 제작