問題文
在高桥的花园里,有一个顶点。 三泽先生是一棵有根树,其根是 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