如何最優化地解決這個問題？

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 

我可以解決每個查詢O(n)使用bfs的時間，但效率不高。我怎樣才能優化這個？我花了很多時間在這個上，但找不到解決方法在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)中找到它。

這種解決方案需要二進制搜索和兩個前綴總和看起坐每查詢，所以它在O(log N)時間。