No.1787 Do Use Dynamic Tree
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
beet
ei1333333