← 返回题目列表

AtCoder · yahoo_procon2018_final_c

C. 树问题

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

配点 : 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