AT_yahoo_procon2018_final_c 木の問題

有一棵包含 $N$ 个顶点的树。第 $i$ 条边连接了顶点 $A_i$ 和 $B_i$。 请回答接下来的 $Q$ 个查询。 - 对于每个查询，求从顶点 $v_i$ 出发，恰好经过 $k_i$ 条边且不经过重复路径（即不回头）的情况下，可以到达的顶点个数。

输入按以下格式从标准输入中给出。 > $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 \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)$ - 输入给出的图是一棵树 - 输入均为整数 ### 样例解释 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$。 由 ChatGPT 4.1 翻译