配点 : 1200 点
問題文
N 个顶点的树。第i 条边的顶点是 A_i 和 B_i 。由
。请回答接下来的 Q 个问题。从
- 頂点 v_i 刚好 k_i 求能够沿着本书的边而不回头地到达的顶点的数量。
制約
- 1 \leq N,Q \leq 10^5
- 1 \leq A_i,B_i \leq N(1\leq i\leq N-1)
- 1 \leq v_i \leq N(1\leq i\leq Q)
- 0 \leq k_i \leq N - 1(1\leq i\leq Q)
- 输入中给出的图是树。
- 输入全部为整数。
入力
输入是按以下格式从标准输入给出的。
N Q
A_1 B_1
:
A_{N-1} B_{N-1}
v_1 k_1
:
v_Q k_Q
出力
每个查询,上游 v_i 刚好 k_i 输出能够沿着本书的边而不回头地到达的顶点的数量。
入力例 1
5 5 2 4 3 1 5 3 2 3 1 0 2 1 3 2 4 4 5 1
出力例 1
1 2 1 0 1
- 1 对于每个查询,边缘 1 刚好 0 能够沿着本书的边到达的顶点只有顶点 1 。因此,1 。 来自
- 2 对于每个查询,边缘 2 刚好 1 能够沿着本书的边到达的顶点只有顶点 2,3 。因此,2 。 来自
- 3 对于每个查询,边缘 3 刚好 2 能够沿着本书的边到达的顶点只有顶点 4 。因此,1 。 来自
- 4 对于每个查询,边缘 4 刚好 4 没有能够沿着本书的边到达的顶点。因此,0 。 来自
- 5 对于每个查询,边缘 5 刚好 1 能够沿着本书的边到达的顶点只有顶点 3 。因此,1 。 来自
入力例 2
7 35 1 2 2 3 1 4 1 5 5 6 5 7 1 0 1 1 1 2 1 3 1 4 2 0 2 1 2 2 2 3 2 4 3 0 3 1 3 2 3 3 3 4 4 0 4 1 4 2 4 3 4 4 5 0 5 1 5 2 5 3 5 4 6 0 6 1 6 2 6 3 6 4 7 0 7 1 7 2 7 3 7 4
出力例 2
1 3 3 0 0 1 2 2 2 0 1 1 1 2 2 1 1 2 3 0 1 3 2 1 0 1 1 2 2 1 1 1 2 2 1