dsu on tree，有名樹上啟發(fā)式合并，是借助重鏈剖分，可以在樹上快速統(tǒng)計(jì)子樹信息的一種算法，只能完成靜態(tài)問題，不支持修改。

假設(shè)我們現(xiàn)在想詢問一個(gè)子樹中某個(gè)顏色的出現(xiàn)次數(shù)，首先我們把詢問掛在節(jié)點(diǎn)上，\(O(n^2)\) 的做法顯然。

我們考慮這樣做：假設(shè)當(dāng)前子樹的根為 \(k\)，我們按照下面的流程：

• 解決所有除了重兒子之外的其它兒子的子樹，并把統(tǒng)計(jì)的信息清零。
• 解決重兒子的子樹，不把統(tǒng)計(jì)信息清零。（注意到我們最多只能不清零一個(gè)子樹的信息）。
• 然后我們統(tǒng)計(jì)其它輕兒子的子樹的信息。
• 回答詢問。
• 若 \(k\) 是重兒子，不清零，否則清零。

考慮這個(gè)算法的復(fù)雜度：

• 首先，重鏈剖分保證了一個(gè)點(diǎn)往上走最多經(jīng)過 \(O(\log n)\) 條輕邊。
• 一個(gè)點(diǎn)的信息被統(tǒng)計(jì)，首先是它的祖先輕邊，其次是遍歷到這個(gè)點(diǎn)，所以一個(gè)點(diǎn)會(huì)被統(tǒng)計(jì) \(O(\log n)\) 次。
• 所以復(fù)雜度是 \(O(n\log n)\)。