시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 1024 MB | 5 | 3 | 3 | 75.000% |
$N$ 개의 정점으로 이루어진 트리가 있다. 정점은 $1$번부터 $N$ 번까지 번호가 매겨져 있다. $i$ 번 정점에는 숫자 $a_i$ 가 쓰여 있다. 초기에는 $a_i = i$ 으로 설정되어 있다.
$f(u, v)$ 를, $u$ 에서 $v$ 로 가는 경로 $p_0 = u, p_1, p_2, \ldots ,p_t = v$ 상에 있는 숫자 $a_{p_0}, a_{p_1}, \ldots, a_{p_t}$ 를 순서대로 늘어 쓴 수열이라고 하자.
다음과 같은 쿼리를 수행해야 한다.
u v
: $a_u, a_v$ 를 바꾼다. 그 후, $f(u, w)$ 를 최대화하는 $w$ 를 출력한다. 수열은 사전순으로 비교한다.쿼리는 온라인으로 주어짐에 유의하라. 자세한 것은 입력 부분을 참고하면 된다.
첫째 줄에 트리의 크기 N이 주어진다. (2 ≤ N ≤ 200,000)
다음 N-1 개의 줄에 두 정수 u, v 가 주어진다. 두 정점 u, v를 잇는 간선이 존재함을 뜻한다. (1 ≤ u, v ≤ N)
다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)
다음 Q개의 줄에 두 정수 x, y가 주어진다. (1 ≤ x, y ≤ n, x ≠ y)
정수 x, y 에서 u, v 를 얻어내기 위해서는 다음과 같이 하면 된다. $last$ 를 직전 쿼리의 정답이라고 하자. (만약 첫 쿼리일 경우 $last = 0$), 이 때 $(u, v) = (((x + N - 1 + last) \text{ mod } N) + 1, ((y + N - 1 + last) \text{ mod } N) + 1)$ 이 성립한다.
Q개의 줄에 걸쳐 문제의 정답을 출력하라.
3 1 2 2 3 4 3 1 3 2 2 1 1 3
1 3 3 3
10 9 8 10 3 2 3 10 9 1 10 6 4 4 1 1 5 6 7 15 8 10 2 8 9 8 8 2 9 1 2 8 1 4 4 1 6 2 6 9 7 8 4 2 4 3 10 2 1 9
2 7 5 8 5 5 5 8 7 8 2 7 5 7 5