페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8671

광덕산 등산 2s 1024MB

문제

디미고의 학생들은 광덕산을 정말 좋아한다. 등산을 좋아하는 M명의 학생들은 원하는 코스를 정해 광덕산을 오르기로 했다.

광덕산에는 N개의 지점이 있고, 각 지점의 고유한 높이 h가 존재한다. 또한, 광덕산에 있는 지점들은 N−1개의 등산로로 연결되며, 임의의 두 지점 사이를 등산로를 통해 오고 갈 수 있다. i번 지점에서 인접한 j번 지점으로 이동할 때 오르막길이라면 A×|h_i−h_j|, 내리막길이라면 B×|h_i−h_j| 만큼 체력을 소모한다. 즉, i에서 j로 이동할 때,

\begin{cases} A×|h_j−h_i| & \text{if} h_i<h_j \\ B×|h_j−h_i| & \text{if} h_i≥h_j \end{cases}

만큼 체력을 소모한다. 광덕산에는 신묘한 힘이 숨겨져 있기 때문에 값이 음수라면 절댓값만큼의 체력을 회복한다.

목적지에 안전하게 도착하려면 이동 중 체력이 0 이상으로 유지되어야 하며, 도착하는 시점에도 체력이 0 이상이여야 한다. M명의 학생들이 초기 체력 c_i로 a_i에서 출발해 b_i까지 이동할 때, 도착할 수 있다면 도착 시점에서의 체력 최댓값을 출력하고, 도착할 수 없다면 -1을 출력하는 프로그램을 작성하시오.


입력

첫 번째 줄에 광덕산에 있는 지점의 개수 N, 오르막 계수 A, 내리막 계수 B가 공백으로 구분하여 주어진다.(2≤N≤2×10^5;−10^6≤A,B≤10^6; A+B≥0)

두 번째 줄에 각 지점의 높이 h_1, h_2,⋯h_N이 공백으로 구분하여 주어진다.(1≤h_i≤10^6)

세 번째 줄부터 N−1개의 줄에 걸쳐 등산로로 연결된 지점 u,v가 공백으로 구분하여 주어진다.(1≤u,v≤N)

광덕산은 항상 올바른 트리 형태로 주어진다.

N+2번째 줄에 학생의 수 M이 주어진다.(1≤M≤2×10^5)

N+3번째 줄부터 M개의 줄에 걸쳐 i번째 학생이 원하는 출발지 a_i와 도착지 b_i, 체력 c_i가 공백으로 구분하여 주어진다.(1≤a_i,b_i≤N;1≤c_i≤10^{18})


출력

M개의 줄에 걸쳐 i번째 줄에 다음과 같이 출력한다. i번째 학생이 도착할 수 있다면, 체력의 최댓값을 출력한다. i번째 학생이 도착할 수 없다면, -1을 출력한다.


예제 

5 2 -1
1 2 3 4 5
1 2
2 3
3 4
4 5
3
1 5 3
5 1 1
1 3 5
-1
5
1

첫 번째 학생은 지점 1에서 지점 2로 이동하는데 체력 2를 소모하고, 체력이 1만큼 남는다. 지점 2에서 지점 3으로 이동하는 과정에서 체력이 −1이 되므로, 목적지로의 도착이 불가능하다.

두 번째 학생은 지점 5에서 지점 1까지 이동하면서 체력은 4만큼 추가되어 5가 된다.

세 번째 학생은 지점 1에서 지점 3으로 이동하면서 4만큼의 체력을 소모하고, 1이 남게 된다.



출처

제 3회 디미고 프로그래밍 챌린지

로그인해야 코드를 작성할 수 있어요.