F - 根付き木のみさわさん Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君の家の庭には、頂点 1 を根とする一本の根付き木である、みさわさんが生えています。

i 日目の朝、みさわさんは M_i 個の頂点 v_{i,1}, …, v_{i,M_i} に実をつけます。

しかし、同じ日の晩には鳥がやってきて、残っているすべての実を食べてしまいます。

高橋君は、一日に一回、みさわさんの頂点をひとつ選んでゆさぶることができます。

頂点 w をゆさぶると、w の子孫 (w 自身も含む) である頂点についている実をすべて得られます。

高橋君は、 i 日目に、みさわさんから K_i 個以上の実を取りたいです。

高いところが好きな高橋君のために、ゆさぶることで K_i 個以上の実を得ることができる頂点のうち、根からもっとも遠いものをもとめ、その根からの距離を教えてください。

ただし、各頂点に対し、根からの距離とは、根からその頂点への唯一の単純なパスに含まれる辺の数を表します。

入力

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

N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
Q
M_1 K_1
v_1_1 v_1_2 ... v_1_{M_1}
:
M_Q K_Q
v_Q_1 v_Q_2 ... v_Q_{M_Q}
  • 1 行目には、みさわさんの頂点の個数を表す整数 N (3≦N≦10^5) が与えられる。
  • 2 行目からの N-1 行のうち i 行目には、i 番目の辺の接続している 2 頂点を表す整数 a_i,b_i (1≦a_i＜b_i≦N) が空白区切りで与えられる。
    • このとき、みさわさんが木であることが保証されている。
  • N+1 行目には、高橋君が実を取りつづける日数を表す整数 Q (1≦Q≦10^5) が与えられる。
  • N+2 行目からの 2Q 行のうち、
    • 2i-1 行目には、i 日目にみさわさんがつける実の数を表す整数 M_i と、高橋君が取りたい実の数を表す整数 K_i (1 ≦ K_i ≦ M_i ≦ N) が与えられ、
    • 2i 行目には、i 日目にみさわさんが実をつける頂点を表す M_i 個の整数が与えられる。
  • 但し、入力は ΣM_i ≦ 10^5 をみたす。

部分点

この問題には部分点が設定されている。

  • 1≦N≦100 を満たすデータセットに正解した場合は 20 点が得られる。
  • 全てのデータセットに正解した場合はさらに 110 点が得られる。合計で 130 点となる。

出力

Q 日分の入力について、条件を満たす頂点のうち、根からもっとも遠い頂点までの距離を、 1 行ずつ出力せよ。 出力の末尾には改行を入れること。

入力例1

5
3 5
1 2
2 3
3 4
3
2 2
4 5
1 1
1
2 1
2 1

出力例1

2
0
1
  • 1 つ目のクエリでは、みさわさんは 2 つの頂点 4,5 に実をつけます。このうち 2 つの実を得られる頂点のうち、もっとも根から遠い頂点は 3 であり、この頂点の根からの距離は 2 です。
  • 2 つ目のクエリでは、みさわさんは 1 つの頂点 1 に実をつけます。このうち 1 つの実を得られる頂点のうち、もっとも根から遠い頂点は 1 であり、この頂点の根からの距離は 0 です。
  • 3 つ目のクエリでは、みさわさんは 2 つの頂点 2,1 に実をつけます。このうち 1 つの実を得られる頂点のうち、もっとも根から遠い頂点は 2 であり、この頂点の根からの距離は 1 です。

入力例2

10
4 10
2 3
1 4
1 2
3 5
1 8
4 6
8 9
2 7
5
10 4
9 7 3 1 5 10 4 6 2 8
2 2
8 2
10 9
6 2 10 4 7 1 5 8 9 3
2 2
10 2
5 1
1 7 2 3 9

出力例2

1
0
0
0
2

入力例3

15
3 4
4 6
11 13
2 6
4 8
7 13
4 7
8 9
1 8
5 9
8 15
9 14
8 12
9 10
5
14 5
5 1 13 8 14 3 2 9 7 10 11 4 12 15
5 5
6 8 12 2 11
1 1
12
12 8
2 13 1 10 12 3 8 9 6 4 7 15
10 8
8 14 13 12 15 10 7 5 2 4

出力例3

2
1
2
1
1