淀粉質(zhì)（點分治）可以用于求樹上路徑統(tǒng)計之類的問題，擴展有 dfs（點分樹）算法

點分治

思想：

每次將重心刪除，將路徑分為經(jīng)過當(dāng)前重心與不經(jīng)過的，然后分成多個聯(lián)通塊，遞歸下去處理即可。

感覺細節(jié)比較多，難寫，而且要用一些小技巧（

代碼太丑了不想放

習(xí)題：

P2634，P3806，P4149，模板

P4178，點分治 + 樹狀數(shù)組

CF914E，點分治 + 狀壓

CF150E，套路，二分中位數(shù)，長鏈/點分治 + 線段樹

點分樹

我們將當(dāng)前聯(lián)通塊重心與上一層重心相連，得到了點分樹

性質(zhì)：

點分樹上兩點的 LCA 必然在原樹兩點路徑上（畫圖就看出來了

點分樹最大深度為 log n（顯然

每個節(jié)點子樹大小和上限?n log n

思想：

綜上，我們得到一個極其暴力的做法：

對于詢問節(jié)點 x，先統(tǒng)計其子樹貢獻。

然后向上一直跳到點分樹根節(jié)點。

假設(shè)從 v 跳到 u，每次增加上在 u?子樹內(nèi)而不在 v?子樹內(nèi)節(jié)點 w?對 x?的貢獻，是 u?子樹對 x 貢獻減去 v?子樹對前者的貢獻

并且因為 u=LCA(x,w)，u?在 x?到 w?路徑上，所以 x?到 w?貢獻能夠被拆為 x?到 u?與 u?到 w 貢獻

對于修改節(jié)點 x，對其每個祖先節(jié)點信息進行修改。

對于每個節(jié)點 x，開一個長為 x 子樹大小的 vector?存信息

相對靈活（

習(xí)題：

P6329，P3241，點分樹

等暑假再更新吧，咕咕咕