問題一覧 > 通常問題

No.1787 Do Use Dynamic Tree

レベル : / AI推定難易度 : 3300 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : beet / テスター : ei1333333
お気に入りにしたユーザー ProblemId : 7509 / 自分の提出
問題文最終更新日: 2021-12-16 01:48:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2021 (順位表) の他の問題:

Problem Statement

You are given a tree with $N$ vertices. The $i$-th edge connects vertex $a_i$ and vertex $b_i$.

Initially, the number $v$ is written on vertex $v$. Let $f(u, v)$ be the sequence obtained by listing, in order, the numbers written on the vertices on the $u-v$ path.

Answer the following query $Q$ times.


  • u v: Swap the numbers written on vertex $u$ and vertex $v$. Then, output $\mathrm{argmax}_w f(u, w)$ (sequences are compared in lexicographic order).

Input

$N$
$a_1\ b_1$
$\vdots$
$a_{N-1}\ b_{N-1}$
$Q$
$u_1\ v_1$
$\vdots$
$u_Q\ v_Q$

(Corrected 2021/12/16 01:47) However, the queries are encrypted. For the $i$-th query, let $x$ be the answer to the previous query ($x = 0$ when $i = 1$), and answer the query with $(u, v) = (((u_i + x) \bmod N) + 1, ((v_i + x) \bmod N) + 1)$.

However, the queries are encrypted. For the $i$-th query, let $x$ be the answer to the previous query ($x = 0$ when $i = 1$), and answer the query with $(u, v) = (((u_i + N - 1 + x) \bmod N) + 1, ((v_i + N - 1 + x) \bmod N) + 1)$.

  • $2 \le N \le 2 \times 10^5$
  • $1 \le a_i, b_i \le N$
  • The given graph is a tree.
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le u_i, v_i \le N$
  • $u_i \neq v_i$

Output

Output $Q$ lines. On the $i$-th line, output the answer to the $i$-th query. Print a newline at the end.

Sample

Sample 1
Input
3
1 2
2 3
4
3 1
3 2
2 1
1 3
Output
1
3
3
3

In the $1$st query, $(u, v) = (3, 1)$. Since $f(3, 1) = (1, 2, 3), f(3, 2) = (1, 2), f(3, 3) = (1)$, output $1$.
In the $2$nd query, $(u, v) = (1, 3)$. Since $f(1, 1) = (1), f(1, 2) = (1, 2), f(1, 3) = (1,2,3)$, output $3$.
In the $3$rd query, $(u, v) = (2, 1)$. Since $f(2, 1) = (1,2), f(2, 2) = (1), f(2, 3) = (1,3)$, output $3$.
In the $4$th query, $(u, v) = (1, 3)$. Since $f(1, 1) = (3), f(1, 2) = (3,1), f(1, 3) = (3,1,2)$, output $3$.

Sample 2
Input
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
Output
2
7
5
8
5
5
5
8
7
8
2
7
5
7
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。