algorithm - 如何最佳解决这个问题？

Question

我有一棵有 n 个顶点的树 n<=10^5其中每个顶点都有一个 score[i] 和 q queries q<=10^5每个查询有两个参数u和L，我需要找到

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

我可以解决 O(n) 中的每个查询时间使用 bfs 但效率不高。我该如何优化呢？我在这上面花了很多时间，但在 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]), upper_bound(at_depth[h + L].begin(), at_depth[h + L].end(), leave_time[u]) 在 C++ 中。

   <

4. 答案是这个范围内的分数总和。我们可以使用前缀和在 O(1) 中找到它。

此解决方案需要二进制搜索和每个查询的两个前缀和查找，因此它在 O(log N) 时间内工作。