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

#4028

제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

광덕산 등산 2초 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이 남게 된다.

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