如何最佳解决这个问题

Question

我有N顶点n<=10^5树，每个顶点都有一个分数[i]和q查询q<=10^5每个查询都有两个参数u和l，我需要找到

sum(score[i]) for all i where lca(i,u)=u and dist(u,i)=L

我可以使用BFS在O(n)时间中解决每个查询，但这不是有效的。我该如何优化？我花了很多时间在这方面，但找不到在nlogn的所有查询中解决它的方法。

任何帮助将不胜感激。谢谢

Answer 1

让u处于深度h。那么，我们需要找到的是u的子树中深度h + L的所有顶点的得分之和（这只是问题的重新汇总）。

1. 让我们存储一个以每个级别的入口时间排序的顶点的向量。

2. 子树是深度h + L的向量中的连续段。

3. 我们可以使用二进制搜索找到其边界（例如lower_bound(at_depth[h + L].begin(), at_depth[h + L].end(), entrance_time[u])，C 中的upper_bound(at_depth[h + L].begin(), at_depth[h + L].end(), leave_time[u])）。

4. 答案是该范围内的得分之和。我们可以在O(1)中使用前缀总和。

此解决方案需要进行二进制搜索，并且每个查询的两个前缀总和查找UPS，因此它在O(log N)时间中起作用。