關于點分治的一些思考

1.點分治的根本原理是分而治之的思想，更準确的是說人工智能中的與或樹問題？

2.點分治的優化源于重心的性質，使得暴力的複雜度得到降低。

3.分治的思想分為找經過目前

r

o

t

root

root的路徑和不經過

root的路徑，不經過

root的路徑可以分治交給子樹處理，是以我們隻需計算出經過

root的路徑即可。

4.在計算某些貢獻時，我們通常有兩種思路，一種是容斥的思想，第二種是對目前

root的不同子樹分别計算貢獻，一般就是開兩個數組維護，有時需要開一個

m

a

p

map

map或棧每次清空，消除影響。

5.比如求權值和

≤

k

\le k

≤k的路徑數，我們可以雙指針計算出經過

root的路徑數，但是這樣的路徑可能有兩條到根的路徑在同一個子樹裡，是以我們需要容斥掉經過該兒子結點對應的貢獻。

6.比如求權值和為

k的路徑數，就可以開兩個數組

[

]

,

n

w

tmp[],now[]

tmp[],now[]，儲存目前子樹的權值和情況，和其他子樹的權值和情況，然後每次計算完目前子樹的貢獻後，更新

now[]

now[]，繼續下一個子樹，每次

c

l

(

)

cal()

cal()後要清空

now[]。

7.對于第二種做法，常常有一些細節，比如要計算單鍊，這時我們需要每次

cal()時初始化

=

1

now[0]=1

now[0]=1。

8.點分治的難點往往在于如何計算貢獻，找到這個問題就解決了。有時需要用到染色，回溯的思想，這類題的比較複雜難想。我就不會，是我太菜了