これを最適に解決する方法は？

Question

各クエリは、2つのパラメータUとLを有している、私は

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

を見つける必要が私は各クエリを解決することができ、私は各頂点がスコアを有するn個の頂点のツリーn<=10^5 [I]を有し、qはq<=10^5 を照会bfsを使用している時間はO(n)ですが、効率的ではありません。これをどのように最適化できますか？私はこれに多くの時間を費やしましたが、すべてのクエリのためにnlogn時間にそれを解決する方法を見つけることができませんでした。

何か助けていただければ幸いです。ありがとう

Answer 1

uを深さhにしましょう。次に、uのサブツリー内の深さh + Lにあるすべての頂点のスコアの合計です（問題の再定式化に過ぎません）。

1. 各レベルの入場時間でソートされた頂点のベクトルを保存しましょう。

2. サブツリーは、深さがh + Lのベクトルの連続セグメントです。

3. バイナリ検索（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])など）を使用して境界線を見つけることができます。

4. 答えはこの範囲のスコアの合計です。接頭辞の合計を使用してO(1)で見つけることができます。

このソリューションでは、バイナリ検索を必要とし、2人のプレフィックスの合計は、クエリごとのアップを見て、それがO(log N)時間で動作します。