트리와 쿼리 23

시간 제한4초메모리 제한1024 MB

요약

트리와 배열 A가 주어졌을 때, 구간 [l, r)의 각 인덱스까지 가중 거리 합을 최소로 하는 정점을 온라인으로 구합니다.

난이도: 어려움10점 중 9점
유형: 트리, 분할 정복, 세그먼트 트리, 이분 탐색
정답자: 아직 제출이 없습니다

문제

$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 \le N \le 150,000$ )

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

다음 줄에 수열 $A_0, A_1, \ldots, A_{N-1}$ 이 주어진다. ( $0 \le A_i \le 150,000$ )

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

다음 $Q$ 개의 줄에 네 정수 $a, b, z, d$ 가 주어진다. ( $0 \le a, b, d \le N-1$ , $0 \le z \le 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$ 개의 줄에 걸쳐 문제의 정답을 출력하라.

예제1

예제 1

입력

5
0 1
1 3
3 2
3 4
1000 10 1 100 10000
15
0 0 0 0
0 1 150000 1
2 0 0 2
3 0 150000 3
4 2 150000 4
1 1 149975 0
0 0 149965 1
1 2 149951 2
1 4 149901 3
3 4 149804 4
2 0 149745 0
3 1 149639 1
1 4 149517 2
4 3 149375 3
0 1 149160 4

예상 출력