????分治法是指將規(guī)模較大的問題分解為規(guī)模較小的子問題，解決各個子問題然后合并得到原問題的答案。樹上的分治算法分為點分治和邊分治。

????分治法的核心是分解和治理。如何分？ 如何治？

????點分治，是一種針對可帶權(quán)樹上簡單路徑統(tǒng)計問題的算法。本質(zhì)上是一種帶優(yōu)化的暴力，帶上一點容斥原理。對于樹上路徑，并不要求這棵樹是有根樹，無根樹不影響統(tǒng)計結(jié)果。

????1. 對于點分治：重心分解

????????數(shù)列上的分治法，通常從數(shù)列中間進行二等分，也就是說分解得到的兩個子問題規(guī)模相當(dāng)。對于樹，怎么劃分呢？

????????樹上的劃分也要盡量均衡，不要出現(xiàn)一個子問題太大，另一個子問題太小的情況。也就是說期望劃分后每個子樹的結(jié)點樹不超過 n/2 。

????????那么選擇哪個結(jié)點作為劃分點呢？

????????可以選擇樹的重心。樹的重心是指刪除該結(jié)點后得到的最大子樹的結(jié)點數(shù)最少。刪除重心后得到的所有子樹，其結(jié)點數(shù)必然不超過 n/2 。

????求樹的重心，只需要進行一次深度優(yōu)先遍歷，找刪除該結(jié)點后最大子樹最小的結(jié)點即可。

????用 f[u] 表示刪除 u 后最大子樹的大小， size[u] 表示以 u 為根的子樹的結(jié)點數(shù), S 表示整棵子樹的結(jié)點數(shù)。先統(tǒng)計 u 的所有子樹中最大子樹的結(jié)點數(shù)，然后與 S-size[u] 比較最大值。如圖所示。

????如果 f[u] < f[root] ，則更新當(dāng)前樹的重心為 root = u。

2.? 邊分治，是指在樹中選一條邊，使得邊的兩端最大子樹盡可能的小，這條邊稱為中心邊。和點分治不同的是，中心邊只會把樹分成2棵子樹，因此處理起來比較方便，，找中心邊的方法和找重心的方法一樣，找使最大子樹盡可能小的那一條邊。

????對于一棵樹，假設(shè)找到的中心邊為 x-y，對于這棵樹中的路徑只有兩種：

• ????經(jīng)過邊 x-y;
  

• ????不經(jīng)過邊 x-y;
  

????不經(jīng)過 x-y 的路徑在某一端的子樹中，只需要遞歸求解即可?，F(xiàn)在只考慮經(jīng)過這條邊的路徑信息，處理完當(dāng)前子樹后，刪掉中心邊，將樹分成2棵樹，再進行遞歸操作。如圖所示。

? ?1）?樹的重建：

點權(quán)：權(quán)值在點上。邊權(quán)：權(quán)值在邊上。

2）求中心邊：

????找中心邊的方法和找重心類似，只需要進行一次深度優(yōu)先遍歷，找刪除該邊后最大子樹最小的邊即可。

????size[u] 表示以 u 為根的子樹的結(jié)點樹， size[rt] 表示以 rt 為根的子樹的所有結(jié)點數(shù)。如圖：?

????如果 max( sz[u]，sz[rt]-sz[u] ) < Max ，則更新 Max ， 中心邊 midedge = code。

3）中心邊分解

????（1）首先求出中心邊 midedge, 得到中心邊的兩個端點 p1,p2，然后刪除 p1 的鄰接邊 midedge^1,刪除 p2的鄰接邊 midedge。如圖所示。

????（2）再分別從 p1,p2出發(fā)遞歸求解；

????（3）更新樹根 rt 的 ans。