問題一覧 > 通常問題

No.1787 Do Use Dynamic Tree

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : beetbeet / テスター : ei1333333ei1333333
1 ProblemId : 7509 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-16 01:48:42

問題文

$N$ 頂点の木が与えられる。$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいる。

はじめ、頂点 $v$ には数 $v$ が書かれている。$f(u, v)$ を $u-v$ パス上の頂点に書かれた数を順に並べた数列とする。

以下のクエリに $Q$ 回答えよ。


  • u v: 頂点 $u$ と頂点 $v$ に書かれた数を入れ替える。その後、$\mathrm{argmax}_w f(u, w)$ を出力する(数列の大小比較は辞書順)

入力

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

(2021/12/16 01:47 修正)ただし、クエリは暗号化されている。$i$ 番目のクエリについて、直前のクエリの答えを $x$ としたとき($i = 1$ のときは $x = 0$ とする)、$(u, v) = (((u_i + x) \bmod N) + 1, ((v_i + x) \bmod N) + 1)$ としてクエリに答えよ。

ただし、クエリは暗号化されている。$i$ 番目のクエリについて、直前のクエリの答えを $x$ としたとき($i = 1$ のときは $x = 0$ とする)、$(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$
  • 与えられるグラフは木をなす
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le u_i, v_i \le N$
  • $u_i \neq v_i$

出力

$Q$ 行出力せよ。$i$ 行目には $i$ 番目のクエリに対する答えを出力せよ。最後に改行せよ。

サンプル

サンプル1
入力
3
1 2
2 3
4
3 1
3 2
2 1
1 3
出力
1
3
3
3

$1$ つ目のクエリでは、$(u, v) = (3, 1)$ となる。$f(3, 1) = (1, 2, 3), f(3, 2) = (1, 2), f(3, 3) = (1)$ であるから、$1$ を出力する。
$2$ つ目のクエリでは、$(u, v) = (1, 3)$ となる。$f(1, 1) = (1), f(1, 2) = (1, 2), f(1, 3) = (1,2,3)$ であるから、$3$ を出力する。
$3$ つ目のクエリでは、$(u, v) = (2, 1)$ となる。$f(2, 1) = (1,2), f(2, 2) = (1), f(2, 3) = (1,3)$ であるから、$3$ を出力する。
$4$ つ目のクエリでは、$(u, v) = (1, 3)$ となる。$f(1, 1) = (3), f(1, 2) = (3,1), f(1, 3) = (3,1,2)$ であるから、$3$ を出力する。

サンプル2
入力
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

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