No.2337 Equidistant
タグ : / 解いたユーザー数 90
作問者 :
SSRS
/ テスター :
ei1333333
👑 
Nachia
問題文
$N$ 頂点の木があり、頂点には $1$ から $N$ までの番号が付けられています。$i$ 番目 ($1 \leq i \leq N - 1$) の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます。
木の $2$ つの頂点 $u, v$ に対し、頂点 $u$ から最小の本数の辺を通って頂点 $v$ へ行くときに通る辺の本数を $d(u,v)$ とします。
$Q$ 個のクエリが与えられます。
$i$ 番目 ($1 \leq i \leq Q$) のクエリでは、木の2つの頂点 $S_i, T_i$ が与えられるので、木の頂点のうち $d(X,S_i)=d(X,T_i)$ となる頂点 $X$ の個数を求めてください。
入力
入力は標準入力から以下の形式で与えられます。
$N$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$
$S_1$ $T_1$
$S_2$ $T_2$
$\vdots$
$S_Q$ $T_Q$
出力
標準出力に $Q$ 行出力してください。$i$ 行目 ($1 \leq i \leq Q$) には $i$ 番目のクエリに対する答えを出力してください。
最後に改行してください。
制約
入力は以下の制約を満たします。
- $2 \leq N \leq 200\,000$
- $1 \leq Q \leq 200\,000$
- $1 \leq A_i \leq N$ ($1 \leq i \leq N-1$)
- $1 \leq B_i \leq N$ ($1 \leq i \leq N-1$)
- 与えられるグラフは木である。
- $1 \leq S_i \leq N$ ($1 \leq i \leq Q$)
- $1 \leq T_i \leq N$ ($1 \leq i \leq Q$)
- $S_i \neq T_i$ ($1 \leq i \leq Q$)
- 入力される値はすべて整数である。
サンプル
サンプル1
入力
7 3 1 2 1 3 2 4 2 5 3 6 3 7 2 3 1 2 4 7
出力
1 0 1
$1$ 番目のクエリでは、$d(X,2)=d(X,3)$ となる $X$ は $1$ のみなので、$1$ 行目には $1$ を出力します。
$2$ 番目のクエリでは、$d(X,1)=d(X,2)$ となる $X$ は存在しないので、$2$ 行目には $0$ を出力します。
$3$ 番目のクエリでは、$d(X,4)=d(X,7)$ となる $X$ は $1$ のみなので、$3$ 行目には $1$ を出力します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。