树中顶点v的第k代后代数量查询：高效解法与问题解决

给定一棵含n个顶点的树（n-1条边），以及q组查询，每组查询包含顶点v和整数k，需要求解顶点v的第k代后代数量。其中n和q的最大值为500000，要求算法时间复杂度为O(N log N)以满足2秒时限。

第k代后代定义：k=1时为v的直接子节点，k=2时为孙节点，以此类推。

输入示例 #

4
1 2
2 3
1 4
3
1 1
1 2
3 1

输出示例 #

2 1 0

解法思路 #

• 最初尝试思路：使用binary-lifting（二进制倍增）和LCA（最近公共祖先）算法，试图寻找深度为v.depth + k且满足LCA(L,R)=v的节点范围，但未成功。
• 正确解法：
  1. 对树进行DFS遍历，记录每个节点的in.time（进入时间戳）、out.time（离开时间戳）以及节点深度。
  2. 按节点深度分组，将同一深度的节点按in.time从小到大排序。
  3. 处理每组查询时：
     • 计算目标深度target_depth = v.depth + k，若目标深度超过树的最大深度，直接返回0。
     • 在目标深度对应的节点列表中，用二分查找找到第一个in.time大于v的in.time的节点下标L；再找到最后一个out.time小于v的out.time的节点下标R。
     • 最终答案为R - L + 1（若R >= L则取该值，否则为0）。

内容的提问来源于stack exchange，提问作者gjeniusz biznesu