← 返回题目列表

AtCoder · tenka1_2015_final_f

F. 有根树三泽桑

中文机器翻译题面 查看原题

問題文

在高桥的花园里,有一个顶点。 三泽先生是一棵有根树,其根是 1 ,生长在这里。

i 第一天早上,三泽同学 M_i 顶点 v_{i,1}, …, v_{i,M_i} 结出硕果。

然而,当天晚上,鸟儿来吃掉所有剩余的水果。

高桥每天可以选择三泽的山峰之一进行摇晃。 当你摇晃

頂点 w 时,w 的后代 (w (包括其本身)。

高桥君, 生活在 i 当天从三泽出发 我想采摘 K_i 以上的水果。

对于热爱高度的高桥来说,通过摇晃它。 K_i 在能够结出超过 1 个果实的顶点中找到距根最远的顶点,并告诉我们它距根的距离。

然而,对于每个顶点,距根的距离表示从根到该顶点的唯一简单路径中包含的边的数量。


入力

输入是按以下格式从标准输入给出的。

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 行是一个整数,表示 Misawa 的顶点数。 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 在第二个查询中,Misawa 说 2 顶点 选择 4,5 结出硕果。其中 2 在能够结出一个果实的顶点中,距根最远的顶点是 3 并且该顶点到根的距离是 2 。
  • 2 在第二个查询中,Misawa 说 1 顶点 选择 1 结出硕果。其中 1 在能够结出一个果实的顶点中,距根最远的顶点是 1 并且该顶点到根的距离是 0 。
  • 3 在第二个查询中,Misawa 说 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