問題一覧 > 通常問題

No.2337 Equidistant

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 90
作問者 : SSRS / テスター : ei1333333 👑 Nachia
3 ProblemId : 5648 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-30 18:22:17

問題文

NN 頂点の木があり、頂点には 11 から NN までの番号が付けられています。ii 番目 (1≤i≤N−11 \leq i \leq N - 1) の辺は頂点 AiA_i と頂点 BiB_i を結んでいます。
木の 22 つの頂点 u,vu, v に対し、頂点 uu から最小の本数の辺を通って頂点 vv へ行くときに通る辺の本数を d(u,v)d(u,v) とします。
QQ 個のクエリが与えられます。
ii 番目 (1≤i≤Q1 \leq i \leq Q) のクエリでは、木の2つの頂点 Si,TiS_i, T_i が与えられるので、木の頂点のうち d(X,Si)=d(X,Ti)d(X,S_i)=d(X,T_i) となる頂点 XX の個数を求めてください。

入力

入力は標準入力から以下の形式で与えられます。 

NN QQ
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
AN−1A_{N-1} BN−1B_{N-1}
S1S_1 T1T_1
S2S_2 T2T_2
⋮\vdots
SQS_Q TQT_Q

出力

標準出力に QQ 行出力してください。ii 行目 (1≤i≤Q1 \leq i \leq Q) には ii 番目のクエリに対する答えを出力してください。
最後に改行してください。

制約

入力は以下の制約を満たします。

  • 2≤N≤200 0002 \leq N \leq 200\,000
  • 1≤Q≤200 0001 \leq Q \leq 200\,000
  • 1≤Ai≤N1 \leq A_i \leq N (1≤i≤N−11 \leq i \leq N-1)
  • 1≤Bi≤N1 \leq B_i \leq N (1≤i≤N−11 \leq i \leq N-1)
  • 与えられるグラフは木である。
  • 1≤Si≤N1 \leq S_i \leq N (1≤i≤Q1 \leq i \leq Q)
  • 1≤Ti≤N1 \leq T_i \leq N (1≤i≤Q1 \leq i \leq Q)
  • Si≠TiS_i \neq T_i (1≤i≤Q1 \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

11 番目のクエリでは、d(X,2)=d(X,3)d(X,2)=d(X,3) となる XX は 11 のみなので、11 行目には 11 を出力します。
22 番目のクエリでは、d(X,1)=d(X,2)d(X,1)=d(X,2) となる XX は存在しないので、22 行目には 00 を出力します。
33 番目のクエリでは、d(X,4)=d(X,7)d(X,4)=d(X,7) となる XX は 11 のみなので、33 行目には 11 を出力します。

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