（從NOI以后一直在各網(wǎng)站上做水題……誰(shuí)叫我這么弱做不動(dòng)難題呢……）
（最近實(shí)在感覺(jué)到弱得令人吃驚……這樣下去還混什么集訓(xùn)隊(duì)啊……于是只好去挑難題了……中間對(duì)某些知識(shí)點(diǎn)有一些見(jiàn)解……就總結(jié)在這里了囧……）
（最近見(jiàn)到了比較多的樹(shù)分治的題目，因此第0個(gè)總結(jié)的就是樹(shù)分治了……）
相關(guān)論文樹(shù)分治用于解決有關(guān)路徑的問(wèn)題。
樹(shù)分治分為點(diǎn)分治和邊分治（其實(shí)還有一種叫“鏈分治”，是樹(shù)的路徑剖分思想的更高級(jí)的體現(xiàn)，一般鏈分治的題目都可以用路徑剖分解決）。點(diǎn)分治就是每次找到重心，然后把重心去掉，對(duì)分成的每?jī)煽脴?shù)之間分別統(tǒng)計(jì)路徑信息（以重心的每個(gè)相鄰點(diǎn)為根，遍歷整棵子樹(shù)即可得到這個(gè)根到每個(gè)結(jié)點(diǎn)的統(tǒng)計(jì)信息），就可以知道包含這個(gè)重心的所有路徑的信息，然后對(duì)于剩下的路徑就是在子樹(shù)里面進(jìn)行同樣的操作了，直到只剩一個(gè)點(diǎn)為止（注意這一個(gè)點(diǎn)所構(gòu)成的路徑有時(shí)也要處理一下）。邊分治就是每次找到一條邊，使得刪掉這條邊后分成的兩棵子樹(shù)大小盡可能平均，然后以刪掉的邊的兩端點(diǎn)為根，分別統(tǒng)計(jì)根到兩棵樹(shù)中的每個(gè)結(jié)點(diǎn)的路徑信息，最后合并算路徑，即可得到包含這條邊的所有路徑的信息，剩下的路徑在兩棵樹(shù)中遞歸處理。
點(diǎn)分治和邊分治是可以通用的，不管樹(shù)上的信息記錄在結(jié)點(diǎn)上還是邊上。這時(shí)一個(gè)很囧的問(wèn)題就出現(xiàn)了：這兩種分治到底哪個(gè)好？這也是本總結(jié)討論的重點(diǎn)。
有關(guān)“哪個(gè)好”的問(wèn)題顯然要從三種復(fù)雜度上考慮。由于點(diǎn)分治和邊分治的空間復(fù)雜度均為O(N)，因此討論空間復(fù)雜度木有意義。所以需要比較的就是時(shí)間復(fù)雜度和編程復(fù)雜度了。
先說(shuō)時(shí)間復(fù)雜度。點(diǎn)分治每次找到重心后，需要將重心刪掉然后分成很多棵子樹(shù)，對(duì)每?jī)煽米訕?shù)之間都要統(tǒng)計(jì)一下。如果操作是可反的（比如計(jì)數(shù)問(wèn)題：統(tǒng)計(jì)某種路徑的條數(shù)），可以通過(guò)先將所有子樹(shù)合在一起統(tǒng)計(jì)，再減去兩端點(diǎn)處在相同子樹(shù)內(nèi)的路徑，但是，如果操作不可反（比如找“最優(yōu)路徑”），就不能這樣做了，只能枚舉所有的子樹(shù)對(duì)。顯然，如果有S棵子樹(shù)，則有O(S
2)個(gè)子樹(shù)對(duì)，最壞情況下（星形的樹(shù)），S=N-1，此時(shí)一一枚舉子樹(shù)對(duì)必然會(huì)導(dǎo)致總時(shí)間復(fù)雜度升到O(N
2)以上。當(dāng)然這是有解決辦法的，可以從小到大枚舉子樹(shù)，每處理完一棵子樹(shù)就將其和前面的合并，此時(shí)算法效率取決于合并的方法。如果使用歸并法（大小為A的和大小為B的合并次數(shù)為A+B），對(duì)于星形樹(shù)的合并總次數(shù)仍然為O(N
2)，如果能保證大小為A的和大小為B的合并次數(shù)為min{A, B}，則可以保證合并總次數(shù)在O(N)以內(nèi)，從而可以保證總時(shí)間復(fù)雜度為O(NlogN)。邊分治由于分成的永遠(yuǎn)是兩棵子樹(shù)，所以在處理子樹(shù)之間的關(guān)系上能夠保證O(N)，問(wèn)題是它并不能保證每次分成的兩棵子樹(shù)大小非常平均，在最壞情況下（星形的樹(shù)），不管刪哪條邊分成的兩棵子樹(shù)大小都是一個(gè)1一個(gè)(N-1)，這樣就會(huì)使總的時(shí)間復(fù)雜度上升為O(N
2)。
從以上的討論中可以看出，點(diǎn)分治和邊分治最怕的都是星形的樹(shù)，也就是那種某個(gè)點(diǎn)的度數(shù)特別大的樹(shù)。相關(guān)論文中提到一種辦法通過(guò)加無(wú)用點(diǎn)的方式將其轉(zhuǎn)化為二叉樹(shù)，從而解決這個(gè)問(wèn)題。這樣一來(lái)，點(diǎn)分治和邊分治的時(shí)間復(fù)雜度都可以保證了。接下來(lái)是編程復(fù)雜度的問(wèn)題：點(diǎn)分治需要找重心（三次DFS或BFS），刪掉重心（需要?jiǎng)h點(diǎn)），且分成最多三棵樹(shù)，需要處理三對(duì)關(guān)系，代碼量肯定大一些，而邊分治只需要算出子樹(shù)大小后就可以找到最優(yōu)邊，并且分成的是兩棵樹(shù)，更重要的是，在有根樹(shù)上刪掉一條邊后，分成的兩棵樹(shù)中有一棵已是有根樹(shù)，另一棵可以通過(guò)扭根的方式將其轉(zhuǎn)化為有根樹(shù)，由于二叉樹(shù)扭根是很方便的，所以就不需要每次重新建樹(shù)，代碼量較小。綜合以上因素，邊分治更好些。
另外，其實(shí)那種加無(wú)用點(diǎn)轉(zhuǎn)化為二叉樹(shù)的方式是有問(wèn)題的，因?yàn)樗淖兞寺窂降囊饬x，可能導(dǎo)致一條路徑由于LCA是無(wú)用點(diǎn)而在統(tǒng)計(jì)時(shí)出現(xiàn)錯(cuò)誤（明明是跨越了重心或最優(yōu)邊的路徑被當(dāng)成木有跨越的），但是……這個(gè)問(wèn)題有一種很簡(jiǎn)單的解決辦法，想知道是什么……AC了ALOEXT再告訴你……
相關(guān)題目：
<1>
(2013年候選隊(duì)互測(cè)•a142857a) 樹(shù) 邊分治，每次找到所有點(diǎn)到根路徑的XOR和，以及特殊點(diǎn)的個(gè)數(shù)，按照特殊點(diǎn)個(gè)數(shù)排序后有序插入Trie，查找即可。
代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 200010, MAXS = 31, INF = ~0U >> 2;
struct edge {
int a, b, pre, next;
} E[MAXN << 1];
struct sss {
int v1, v2;
bool operator< (sss s0) const {return v1 < s0.v1;}
} S1[MAXN], S2[MAXN];
int T[MAXN * MAXS][2];
int n, m0, K, sum0, __No, N, A[MAXN], Q[MAXN], ls[MAXN], L[MAXN], R[MAXN], pr[MAXN], SZ[MAXN], V1[MAXN], V2[MAXN], res = -1;
bool B[MAXN], vst[MAXN];
void init_d()
{
re(i, n) E[i].pre = E[i].next = i; if (n & 1) m0 = n + 1; else m0 = n;
}
void add_edge(int a, int b)
{
E[m0].a = a; E[m0].b = b; E[m0].pre = E[a].pre; E[m0].next = a; E[a].pre = m0; E[E[m0].pre].next = m0++;
E[m0].a = b; E[m0].b = a; E[m0].pre = E[b].pre; E[m0].next = b; E[b].pre = m0; E[E[m0].pre].next = m0++;
}
void init()
{
scanf("%d%d", &n, &K); init_d();
int x, y;
re(i, n) {scanf("%d", &x); B[i] = x;}
re(i, n) scanf("%d", &A[i]);
re2(i, 1, n) {scanf("%d%d", &x, &y); add_edge(--x, --y);}
}
int dfs0(int l, int r)
{
if (l > r) return -1; else if (l == r) return ls[l]; else {
int n0; if (!l && r == sum0 - 1) n0 = __No; else n0 = n++;
int mid = l + r >> 1, lch = dfs0(l, mid), rch = dfs0(mid + 1, r);
L[n0] = lch; R[n0] = rch; pr[lch] = pr[rch] = n0; return n0;
}
}
void prepare()
{
int x, y; Q[0] = 0; vst[0] = 1; pr[0] = -1;
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front]; sum0 = 0;
for (int p=E[x].next; p != x; p=E[p].next) {
y = E[p].b;
if (!vst[y]) {ls[sum0++] = y; vst[y] = 1; Q[++rear] = y;}
}
if (sum0 > 1) {__No = x; dfs0(0, sum0 - 1);} else if (sum0 == 1) {L[x] = ls[0]; pr[ls[0]] = x; R[x] = -1;} else L[x] = R[x] = -1;
}
}
void solve(int No, int n0)
{
if (n0 == 1) {
if (B[No] >= K && A[No] > res) res = A[No];
return;
}
int x, _x, y, minv = INF, _n0 = n0 >> 1; Q[0] = No;
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
if ((y = L[x]) >= 0) Q[++rear] = L[x];
if ((y = R[x]) >= 0) Q[++rear] = R[x];
}
rre(i, n0) {
x = Q[i]; SZ[x] = 1;
if (L[x] >= 0) SZ[x] += SZ[L[x]];
if (R[x] >= 0) SZ[x] += SZ[R[x]];
if (SZ[x] <= _n0 && _n0 - SZ[x] < minv || SZ[x] > _n0 && SZ[x] - _n0 < minv) {minv = SZ[x] <= _n0 ? _n0 - SZ[x] : SZ[x] - _n0; _x = x;}
}
x = pr[_x]; pr[_x] = -1; if (L[x] == _x) L[x] = -1; else R[x] = -1;
int sum0 = 1; ls[0] = x; while ((y = pr[x]) != -1) {if (L[y] == x) L[y] = -1; else R[y] = -1; if (L[x] == -1) L[x] = y; else R[x] = y; x = ls[sum0++] = y;}
pr[ls[0]] = -1; re2(i, 1, sum0) pr[ls[i]] = ls[i - 1];
int len1 = 0, len2 = 0;
Q[0] = _x; V1[_x] = B[_x]; V2[_x] = A[_x]; S1[len1].v1 = V1[_x]; S1[len1++].v2 = V2[_x];
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
if ((y = L[x]) >= 0) {Q[++rear] = y; V1[y] = V1[x] + B[y]; V2[y] = V2[x] ^ A[y]; S1[len1].v1 = V1[y]; S1[len1++].v2 = V2[y];}
if ((y = R[x]) >= 0) {Q[++rear] = y; V1[y] = V1[x] + B[y]; V2[y] = V2[x] ^ A[y]; S1[len1].v1 = V1[y]; S1[len1++].v2 = V2[y];}
}
Q[0] = ls[0]; V1[ls[0]] = B[ls[0]]; V2[ls[0]] = A[ls[0]]; S2[len2].v1 = V1[ls[0]]; S2[len2++].v2 = V2[ls[0]];
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
if ((y = L[x]) >= 0) {Q[++rear] = y; V1[y] = V1[x] + B[y]; V2[y] = V2[x] ^ A[y]; S2[len2].v1 = V1[y]; S2[len2++].v2 = V2[y];}
if ((y = R[x]) >= 0) {Q[++rear] = y; V1[y] = V1[x] + B[y]; V2[y] = V2[x] ^ A[y]; S2[len2].v1 = V1[y]; S2[len2++].v2 = V2[y];}
}
sort(S1, S1 + len1); sort(S2, S2 + len2); int _len2 = len2 - 1;
N = 1; T[1][0] = T[1][1] = 0; int v0, _v;
re(i, len1) {
while (_len2 >= 0 && S1[i].v1 + S2[_len2].v1 >= K) {
v0 = S2[_len2--].v2; x = 1;
rre(j, MAXS) {
y = (v0 & (1 << j)) > 0;
if (!T[x][y]) {T[x][y] = ++N; T[N][0] = T[N][1] = 0;}
x = T[x][y];
}
}
if (T[1][0] || T[1][1]) {
v0 = S1[i].v2; x = 1; _v = 0;
rre(j, MAXS) {
y = (v0 & (1 << j)) > 0; _v <<= 1;
if (T[x][!y]) {x = T[x][!y]; _v++;} else x = T[x][y];
}
if (_v > res) res = _v;
}
}
x = _x; y = ls[0];
solve(x, len1); solve(y, len2);
}
void pri()
{
printf("%d\n", res);
}
int main()
{
init();
prepare();
solve(0, n);
pri();
return 0;
}
<2>
(VK Cup 2012 R1-D) Distance in Tree邊分治，很容易實(shí)現(xiàn)，不說(shuō)了。
代碼：不顯示。