No.3825 Jump
タグ : / 解いたユーザー数 15
作問者 :
shiomusubi496
/ テスター :
Rho
問題文
$1, 2, \ldots, N$ の $N$ 個の頂点からなる木 $T$ が与えられます。$i = 1, 2, \ldots, N-1$ について、$i$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます。頂点 $u$ から頂点 $v$ へと移動するために通る必要がある最小の辺の本数を $\mathrm{dist}(u, v)$ とします。
この木を用いて Alice と Bob がゲームを $Q$ 回行います。$i$ 番目のゲームにおいて頂点 $A_i, B_i$ $(2 \leq A_i \leq N, 2 \leq B_i \leq N)$ が指定されます。
はじめ Alice は自分の駒を頂点 $A_i$ に、Bob は自分の駒を頂点 $B_i$ に置きます。Alice から始めて次の操作を交互に繰り返します。
- 自分の駒が頂点 $x$、相手の駒が頂点 $y$ にあるとする。$\mathrm{dist}(x, v) \leq \mathrm{dist}(y, v)$ を満たす頂点 $v$ に自分の駒を動かす。なお、$v=x$ としても良い。
先に頂点 $1$ に自分の駒を置いた方が勝ちです。このとき、Alice と Bob のいずれか片方は、相手がどのような操作を行った場合も適切に操作を行えば有限回の操作で必ず勝てることが証明できます。
$Q$ 回のゲームでそれぞれどちらが必ず勝てるかを判定してください。
入力
$N$
$U_1\ V_1$
$U_2\ V_2$
$\vdots$
$U_{N-1}\ V_{N-1}$
$Q$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_Q\ B_Q$
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq U_i < V_i \leq N$ $(1 \leq i \leq N)$
- 与えられるグラフは木をなす
- $1 \leq Q \leq 2 \times 10^5$
- $2 \leq A_i \leq N$ $(1 \leq i \leq Q)$
- $2 \leq B_i \leq N$ $(1 \leq i \leq Q)$
- 入力は全て整数
出力
$Q$ 行にわたって出力してください。
$i$ 行目には、$i$ 回目のゲームで Alice が必ず勝てる場合 Alice を、Bob が必ず勝てる場合 Bob を一行に出力してください。
サンプル
サンプル1
入力
5 1 2 2 3 2 4 3 5 1 5 4
出力
Bob
ゲームは $1$ 回行われます。このゲームは例えば次のように進行します。
- はじめ、Alice は頂点 $5$ に、Bob は頂点 $4$ に駒を置いている。
- $\mathrm{dist}(5, 3) = 1 \leq 2 = \mathrm{dist}(4, 3)$ を満たすため、Alice が頂点 $5$ から頂点 $3$ に駒を動かす。
- $\mathrm{dist}(4, 1) = 2 \leq 2 = \mathrm{dist}(3, 1)$ を満たすため、Bob が頂点 $4$ から頂点 $1$ に駒を動かす。
- Bob が頂点 $1$ に駒を動かしたため、Bob が勝利する。
この進行で互いに最適に行動しているとは限らないことに注意してください。
Alice がどのように行動をしても Bob は勝つことができるため、Bob と出力します。
サンプル2
入力
2 1 2 1 2 2
出力
Alice
$\mathrm{dist}(2, 1) \leq \mathrm{dist}(2, 1)$ なので、Alice は一回目の操作で頂点 $1$ に駒を動かすことができます。
サンプル3
入力
5 1 2 2 3 1 4 4 5 5 3 5 5 2 5 4 2 4 4 3
出力
Alice Bob Bob Alice Alice
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。