U247382 讲课例题

你有一棵 $n$ 节点的树 $T$，回答 $m$ 个询问，每次询问给你两个整数 $l,r$，问存在多少个整数 $k$ 使得从树上编号为 $l$ 的点沿着 $l\to r$ 的简单路径走 $k$ 步恰好到达 $k$。

第一行，两个整数 $n,m$ 表示节点数和询问数。 之后 $n-1$ 行，每行两个整数 $u,v$ 表示一条边。 之后 $m$ 行，每行两个整数 $l,r$ 表示 一个询问，题意同题目描述。

$m$ 行，对于每个询问单独输出一行表示你的答案。

 如图，红色表示第一次询问中 $k=0,1,\ldots,4$ 的情况，蓝色表示第二次询问，绿色是第三次询问。 其中，在第一次询问中： - 走 $0$ 步到达 $6$，不符题意。 - 走 $1$ 步到达 $1$，满足题意。 - 走 $2$ 步到达 $4$，不符题意。 - 走 $3$ 步到达 $3$，满足题意。 - 走 $4$ 步到达 $7$，不符题意。 ### 数据范围 | 测试点编号 | $n\le$ | $m\le$ | 特殊性质 | | ----------- | -------------- | -------------- | -------- | | $1\sim 3$ | $10$ | $10$ | ACD | | $4\sim 6$ | $100$ | $100$ | ACD | | $7\sim 10$ | $500$ | $500$ | ABCD | | $11\sim 13$ | $10^4$ | $10^4$ | ABD | | $14\sim 16$ | $10^5$ | $10^5$ | ABD | | $17\sim 20$ | $3\times 10^5$ | $3\times 10^5$ | CDDD | 其中特殊性质一栏中，每个字符分别表示该测试点满足的性质。例如 $4\sim 6$ 行中的"ACD"表示#4满足A，#5满足C，#6 满足 D。 - A： 一条链 - B： 深度不超过 $50$ - C： 将 $1$ 作为根时会形成一棵二叉树 - D： 无性质