如何最佳解决这个问题？
How to solve this optimally?
我有一棵包含 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 时间内解决所有查询的方法。
感谢任何帮助。谢谢
设 u 深度为 h。那么我们需要找到的是 u 的子树中深度为 h + L 的所有顶点的分数之和（这只是问题的重新表述）。
让我们存储一个顶点向量，按每个级别的进入时间排序。
子树是深度 h + L 向量中的连续片段。
我们可以使用二进制搜索找到它的边界（类似于 C++ 中的 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])）。
答案是这个范围内分数的总和。我们可以使用前缀和在 O(1) 中找到它。
此解决方案需要二进制搜索和每个查询的两个前缀和查找，因此它在 O(log N) 时间内有效。
我有一棵包含 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 时间内解决所有查询的方法。
感谢任何帮助。谢谢
设 u 深度为 h。那么我们需要找到的是 u 的子树中深度为 h + L 的所有顶点的分数之和（这只是问题的重新表述）。
让我们存储一个顶点向量，按每个级别的进入时间排序。
子树是深度
h + L向量中的连续片段。我们可以使用二进制搜索找到它的边界（类似于 C++ 中的
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])）。答案是这个范围内分数的总和。我们可以使用前缀和在
O(1)中找到它。
此解决方案需要二进制搜索和每个查询的两个前缀和查找，因此它在 O(log N) 时间内有效。