1547: 树上询问 SDAFSSDAF

Question

1547: 树上询问
题目描述
你有一棵 n
节点的树 T
，回答 m
个询问，每次询问给你两个整数 l,r
，问存在多少个整数 k
使得从 l
沿着 l→r
的简单路径走 k
步恰好到达 k
。
输入
第一行，两个整数 n,m
表示节点数和询问数。
之后 n−1
行，每行两个整数 u,v
表示一条边。
之后 m
行，每行两个整数 l,r
表示 一个询问，题意同题目描述。
输出
m
行，对于每个询问单独输出一行表示你的答案。
样例输入 复制
9 3
5 4
4 3
3 7
4 1
1 6
1 8
1 9
5 2
6 7
2 3
3 2
样例输出 复制
2
1
0
提示
【样例解释】

如图，红色表示第一次询问中 k=0,1,…,4
的情况，蓝色表示第二次询问，绿色是第三次询问。
其中，在第一次询问中：

• 走 0
  步到达 6
  ，不符题意。
• 走 1
  步到达 1
  ，满足题意。
• 走 2
  步到达 4
  ，不符题意。
• 走 3
  步到达 3
  ，满足题意。
• 走 4
  步到达 7
  ，不符题意。
  【数据范围】

其中特殊性质一栏中，每个字符分别表示该测试点满足的性质。例如 4∼6
行中的"ACD"表示#4满足A，#5满足C，#6满足D。

• A： 一条链

• B： 深度不超过 50

• C： 将 1
  作为根时会形成一棵二叉树

• D： 无性质

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如需一对一服务私聊我哦

题目分析 根据题意，对于每个询问，需要在以$l$为根节点的子树中，求出有多少条简单路径$i\rightarrow j$满足从$i$开始走$k$步可以到达$j(k\in\mathbb{Z})$。对于每条路径，只要确定它们的起点和终点，就可以计算出它们满足要求的$k$的数量了。 考虑利用路径结构去优化计算。对于每个节点，选取一个代表距离它最近的满足$\mathrm{dep}(v)-\mathrm{dep}(u)\equiv \mathrm{dist}(u,v)\pmod{2}$的节点$u$。在这个前提下，从$u$向上走$i$步，再向下拐走$j-i$步，最终得到的一条路径就满足了要求。具体实现可以看代码。 最后需要补充一点，就是一个节点不一定完全覆盖了它所代表的深度范围，可能只包含了其中一部分。因此需要特别对这种情况处理，也可以看代码。 代码实现 这里提供基于倍增的实现方式，实际上还有LCA在线求解和树链剖分两种实现方式，博客上应该也会有介绍。