智乃的点分树（模板）

题号：NC236189
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

给定一颗大小为 $N$ 的无根树，节点编号从 $1$ 到 $N$ ，定义树上两点间的距离 $dis(u,v)$ 为从 $u$ 到 $v$ 的唯一最短路径上边的数目。

特别的，我们认为一个节点距离它自身的距离为 $0$ ，即 $dis(u,u)=0$ 。

定义无根树上的点集 $U(r,d)=\{x:dis(r,x) \leq d\}$ 。

现在智乃酱要进行 $m$ 次查询，每次查询给定两个参数 $r,d$ ，请你告诉智乃酱集合 $U(r,d)$ 的尺寸 $|U(r,d)|$ 是多少，智乃酱要求你使用点分树解决本题，所以对于每次的查询参数 $r$ 将会通过强制在线的方式给出。

第一行是两个整数表示节点数以查询的次数。
接下来输入行，每行两个正整数表示树的一条边。
接下来行，每行两个整数，表示强制在线参数以及距离。

真正的查询参数由下列公式求得：
其中表示上一次查询的答案，并且在一开始的值为

输出行，对于每个查询，输出答案。

示例1

复制

复制

1
6
2

解密后的3个查询分别为：
2 0
3 1
2 1