2C. 미터원기 (Meter Standard)

문제

인덱스국 문화사 : Day 2

인덱스국은 N개의 도시들이 N − 1개의 양방향 도로로 연결되어 있고, 임의의 두 도시를 도로를 이용해 이동할 수 있는 나라로, 1번 도시를 수도로 두고 있습니다. 인덱스국은 길이의 단위로 미터를 사용하는데, 각 도시에 금속으로 만든 미터원기를 두고 측정하러 온 사람들에게 길이 인증서를 발급해줍니다.

그러나 금속으로 만든 미터원기는 온도에 의해 길이가 변화한다는 문제점이 있습니다. 각 도시의 미터원기는 모두 다른 금속으로 만들어져 있고, 도시 i의 미터원기는 절대온도 $T = 0$ 에서의 길이 $L_i$ 와 팽창률 $\alpha_i$ 를 가집니다. 참고로 절대온도 $T$ 에서 미터원기의 길이는 $L_i(1 + \alpha_iT)$ 로 계산할 수 있습니다. 도시 $x$ 가 도시 $y$ 보다 수도에 더 가까울 경우(도시 $y$ 에서 수도까지 가는데 도시 $x$ 를 무조건 지나야 할 경우) 도시 $x$ 의 미터원기는 도시 $y$ 의 미터원기보다 더 고오급이기 때문에 온도 변화당 길이 변화가 작거나 같습니다. ( $L_x\alpha_x \leq L_y\alpha_y$ ) 도시 $i$ 의 미터원기는 녹는점 $m_i$ 를 가지고 있습니다. 도시 $i$ 의 온도가 $m_i$ 를 초과할 경우 이 도시의 미터원기는 냉동실에 옮겨져 하루 동안 사용할 수 없게 됩니다. 단, 수도의 미터원기는 고오오급 미터원기이기 때문에 절대로 녹지 않습니다. ( $m_1 = 10^9$ ) 탐레프는 최근에 IDTforces의 G번 문제를 풀기 위해 인덱스 트리를 사용하여 본국에서 추방 당하고 인덱스국으로 망명한 천재 과학자입니다. 하지만 과학따위는 학문으로 쳐주지 않는 인덱 스국에서 탐레프는 무능력했고, 결국 인덱스 트리 업자로 하루하루 먹고사는 신세가 되었습니다.

인덱스 트리 업자란 인덱스 트리를 만들어 길이에 비례한 가격에 인덱스 트리를 파는 일을 하는 사람입니다. 인덱스 트리의 가격을 결정하는 길이는 미터원기를 기준으로 측정한 길이입니다.

탐레프는 $i$ 일에 $x_i$ 번 도시에서 인덱스 트리를 만든 후, 최단거리로 수도로 운반하여 판매합니다. 탐레프는 인덱스 트리를 최대한 비싸게 팔고 싶기 때문에, 수도로 운반하던 길 중간에 있는 도시들 중 가장 미터원기가 짧은 도시에서 길이를 측정하고자 합니다. 탐레프는 프로그래밍에도 천재였기 때문에 매일 수도로 운반하는 길 중간에서 가장 짧은 미터원기의 길이를 빠르게 구하는 프로그램을 만드려고 했지만, 인덱스 트리를 만드는 일이 매우 힘들어서 여러분에게 프로그램을 만들어달라고 부탁했습니다.

구현 세부 사항

다음 함수들을 구현하세요.

void init(int S[], int E[], int L[], int La[], int M[])

이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
S, E는 크기 N − 1의 배열입니다. 모든 0 ≤ i ≤ N − 2에 대해 S[i]와 E[i] 사이에 양방향 도로가 존재합니다.
L, La, M 은 크기 N 의 배열입니다. 모든 0 ≤ i ≤ N − 1에 대해 $L_{i+1}$ = L[i], $L_{i+1}\alpha_{i+1}$ = La[i], $m_{i+1}$ = M[i]를 만족합니다.

int64 minStandard(int X, int T)

이 함수는 Q번 호출되며, 오늘의 작업 도시가 X, 온도가 T일 때 가장 짧은 미터원기의 길이를 반환해야 합니다.

제한 조건

1 ≤ N ≤ 80,000
0 ≤ Q ≤ 160,000
1 ≤ L[i], La[i] ≤ 109 (0 ≤ i ≤ N − 1)
도시 y에서 수도까지 가는데 도시 x를 무조건 지나야 할 경우 La[x − 1] ≤ La[y − 1]
M[0] = $10^9$ , 1 ≤ M[i] ≤ $10^9$ (1 ≤ i ≤ N − 1)
0 ≤ T ≤ $10^9$
1 ≤ S[i], E[i], X ≤ N (0 ≤ i ≤ N − 2)
임의의 두 도시를 양방향 도로들을 이용해서 이동할 수 있습니다.

서브태스크

서브태스크	점수	제한 조건
1	2	`Q` ≤ 2,000
2	6	`M[i]` = $10^9$
3	6	`N` ≤ 40,000
4	6	추가 제한 조건 없음

예제 입출력

N = 5, S = [1, 1, 2, 2], E = [2, 3, 4, 5], L = [5, 4, 3, 2, 1], La = [1, 2, 3, 4, 5], M = [1e9, 2, 4, 5, 2]

그레이더는 다음 함수를 호출합니다.

init(5, [1, 1, 2, 2], [2, 3, 4, 5], [5, 4, 3, 2, 1], [1, 2, 3, 4, 5], [1e9, 2, 4, 5, 2])

minStandard(4, 0) = 2

minStandard(4, 2) = 7

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받습니다.

line 1 : N Q
line 2 : L[0] L[1] ··· L[N − 1]
line 3 : La[0] La[1] ··· La[N − 1]
line 4 : M[0] M[1] ··· M[N − 1]
line 5 + i (0 ≤ i ≤ N − 2) : S[i] E[i]
line N + 4 + i (0 ≤ i ≤ Q − 1) : X[i] T[i]