트리와 쿼리 23

$N$ 개의 정점으로 이루어진 트리가 있다. 정점은 $0$번부터 $N-1$ 번까지 번호가 매겨져 있다. 추가로, 길이 $N$ 의 정수 수열 $A\_0, A\_1, \ldots, A\_{N - 1}$ 이 주어진다.

$0 \le l < r \le N$ 을 만족하는 정수 $l, r$, 그리고 정점 $v, d$, 음이 아닌 정수 $k$ 에 대해 $f(l, r, v, d, k) = 10^{-999999999} dist(v, d) + \sum\_{i = l}^{r - 1} (A\_i + k) dist(v, i)$ 로 정의하자. 여기서 $dist(a, b)$ 는 두 정점 $a, b$ 를 잇는 최단 경로의 길이이다.

다음과 같은 쿼리를 수행해야 한다.

• l r d k: $f(l, r, v, d, k)$ 를 최소화하는 $v$ 를 출력하라. 이러한 $v$ 가 유일함을 증명할 수 있다.

쿼리는 온라인으로 주어짐에 유의하라. 자세한 것은 입력 부분을 참고하면 된다.

첫째 줄에 트리의 크기 N이 주어진다. (1 ≤ N ≤ 150,000)

다음 N-1 개의 줄에 두 정수 u, v 가 주어진다. 두 정점 u, v를 잇는 간선이 존재함을 뜻한다. (0 ≤ u, v ≤ N-1)

다음 줄에 수열 A0, A1, ..., An-1 이 주어진다. (0 ≤ Ai ≤ 150,000)

다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 150,000)

다음 Q개의 줄에 네 정수 a, b, z, d가 주어진다. (0 ≤ a, b, d ≤ n - 1, 0 ≤ z ≤ 150,000)

$X\_i$ 를 $i$ 번 쿼리에 대한 답이라고 하자 ($0 \le i \le Q - 1$). $i$ 번 쿼리에 대해, $l, r, k$ 는 다음과 같은 식에 의해 복원할 수 있다. $d$ 는 입력으로 주어진 것을 그대로 사용하면 된다.

• $a^\prime = (a + \sum\_{j = 0}^{i - 1} X\_j) \text{ mod } N$
• $b^\prime = (b + 2 \sum\_{j = 0}^{i - 1} X\_j) \text{ mod } N$
• $k = (z + (\sum\_{j = 0}^{i - 1} X\_j)^2) \text{ mod } 150\\,001$
• $l = min(a^\prime, b^\prime)$
• $r = 1 + max(a^\prime, b^\prime)$

$Q$ 개의 줄에 걸쳐 문제의 정답을 출력하라.