【1】新型LCA算法：（在WJMZBMR神犇空間上發(fā)現(xiàn)的，系神犇自創(chuàng)，Orz！！！）
這種算法可以在僅使用樹的路徑剖分預(yù)處理中求出的DEP和UP來求任意兩點(diǎn)的LCA，時間復(fù)雜度為O(log
2N)，不需要單獨(dú)的預(yù)處理。
步驟（假設(shè)求a0、b0兩點(diǎn)的LCA）：
（1）若UP[a0]==UP[b0]，則a0、b0位于同一條重鏈上，顯然a0、b0中深度小的那個就是LCA了，返回結(jié)果，結(jié)束；
（2）若UP[a0]!=UP[b0]且DEP[UP[a0]]>=DEP[UP[b0]]，則
LCA不可能在a0所在的那條重鏈上。證明：若LCA在a0所在的重鏈上，則UP[a0]必然也是a0、b0的公共祖先，也就是UP[a0]是b0的祖先。由于UP[a0]的深度大于等于UP[b0]，若DEP[UP[a0]]>DEP[b0]，則UP[a0]顯然不可能是b0的祖先，否則，在b0所在的重鏈上必然存在一個點(diǎn)C，滿足DEP[C]=DEP[UP[a0]]，顯然，C也是b0的祖先，這就說明在樹中同一深度處存在兩個不同的結(jié)點(diǎn)，它們都是b0的祖先，這是不可能的，所以，LCA不可能在a0所在重鏈上。那么，a0就可以上溯到UP[a0]的父結(jié)點(diǎn)處（也就是E[FA[UP[a0]]].a），b0不動，然后繼續(xù)判斷；
（3）若UP[a0]!=UP[b0]且DEP[UP[a0]]<DEP[UP[b0]]，則LCA不可能在b0所在的重鏈上，將b0上溯到E[FA[UP[b0]]].a，a0不動，繼續(xù)判斷。
由于a0、b0最多上溯O(log
2N)次，所以該算法一定能在O(log
2N)時間內(nèi)求出LCA(a0, b0)。
該算法的應(yīng)用很廣，不光可以在樹的路徑剖分中快速求出LCA，精簡代碼，同時也減少了一些時間（因?yàn)樗恍枰馬MQ那樣進(jìn)行預(yù)處理），而且，在一般的求LCA問題中，也可以先剖分求出UP再求LCA。
代碼：
int LCA(int a, int b)
{
while (1) {
if (UP[a] == UP[b]) return DEP[a] <= DEP[b] ? a : b;
else if (DEP[UP[a]] >= DEP[UP[b]]) a = E[FA[UP[a]]].a; else b = E[FA[UP[b]]].a;
}
}
【2】樹的路徑剖分模板總結(jié)：
（1）預(yù)處理部分：由于采用新型LCA算法（注意，求LCA的過程寫成專門的函數(shù)），所以，原來預(yù)處理部分的后3步都不需要了，也就是只要前3步：第一步建有根樹求出FA、DEP；第二步求出SZ劃分輕重邊；第三步找重鏈建線段樹求出UP、ord、tot和root。那些為了求RMQ而設(shè)置的數(shù)組也不需要了。
（2）操作部分：難點(diǎn)在于上溯過程和銜接。設(shè)待操作的路徑為a0->b0（注意是有向的，
無向的也可以當(dāng)成有向的處理），LCA0=LCA(a0, b0)；對于點(diǎn)權(quán)型的樹，a0->LCA0的過程需要包含LCA0，而b0->LCA0的過程不能包含LCA0。因此當(dāng)b0==LCA0時，第二步應(yīng)該什么事都不做，所以要特判；此外，如果N==1（樹中只有一個結(jié)點(diǎn)），為了防止引用根的父結(jié)點(diǎn)，也需要直接特判掉，所以，上溯過程可以分以下4步：
<1>特判：若n=1（此時必然有a0==b0==0），直接操作0號結(jié)點(diǎn)，結(jié)束；
<2>(a0->LCA)若a0是父邊是輕邊的葉結(jié)點(diǎn)，則單獨(dú)處理a0，最新點(diǎn)設(shè)為a0，a0跳到a0的父結(jié)點(diǎn)處開始，否則從a0開始（上溯）。上溯終止條件為DEP[a0]<DEP[LCA0]或者上溯到根結(jié)點(diǎn)，每次處理時，設(shè)c=”UP[a0]不超越LCA?UP[a0]:LCA"，對[c, a0]段處理（l0=ord[c], r0=ord[a0]），再將a0上溯到c的父結(jié)點(diǎn)處（若c是根結(jié)點(diǎn)則退出）；處理時，線段樹中記錄的所有有向的（從左到右的）信息都要反向；銜接時應(yīng)不斷向右銜接；
<3>(b0->LCA)與<2>類似，兩個不同點(diǎn)：一是有向的信息不要反向，銜接時應(yīng)不斷向左銜接；二是若c==LCA，則l0=ord[c]+1；
<4>最后將<2>中和<3>中得到的兩個銜接鏈再銜接一下即可；
對于邊權(quán)型的樹，a0->LCA0的過程和b0->LCA0的過程都要包含LCA0引出的邊，b0==LCA0以及N==1時不需要特判（因?yàn)樗鼈儠詣拥厥裁词露疾蛔觯辉谔幚磉^程中，l0=ord[c], r0=ord[a0]-1；要分輕邊和重鏈分別處理；每次a0上溯到c而不是c的父結(jié)點(diǎn)處；終止條件為DEP[a0]<=DEP[LCA0]。
模板題：
PKU2831（動態(tài)最小生成樹問題，需要涉及到最小生成樹中兩點(diǎn)之間路徑上的最大邊權(quán)，用樹的路徑剖分。其實(shí)本題有離線算法，不需要樹的路徑剖分）
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
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--)
const int MAXN = 1001, MAXM = 100001, INF = ~0U >> 2;
struct _edge {
int a, b, w;
} _E[MAXM], _E2[MAXM];
struct edge {
int a, b, w, pre, next;
bool Z;
} E0[MAXN << 2], E[MAXN << 2];
struct node {
int maxw, lch, rch;
} T[MAXN << 2];
int n, _m, m0, m, N, u[MAXN], Q[MAXN], FA[MAXN], DEP[MAXN], SZ[MAXN], UP[MAXN], ord[MAXN], w0[MAXN], tot[MAXN], root[MAXN], l0, r0, x0, res;
bool vst[MAXN];
void init_d()
{
re(i, n) E0[i].pre = E[i].pre = E0[i].next = E[i].next = i;
m0 = m = n;
}
void add_edge0(int a, int b, int w)
{
E0[m0].a = a; E0[m0].b = b; E0[m0].w = w; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
E0[m0].a = b; E0[m0].b = a; E0[m0].w = w; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void add_edge(int a, int b, int w)
{
E[m].a = a; E[m].b = b; E[m].w = w; E[m].Z = 0; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
int cmp(const void *s1, const void *s2)
{
return ((_edge *)s1)->w - ((_edge *)s2)->w;
}
int UFS_find(int x)
{
int r = x, tmp; while (u[r] >= 0) r = u[r]; while (u[x] >= 0) {tmp = u[x]; u[x] = r; x = tmp;} return r;
}
void UFS_union(int x1, int x2)
{
if (u[x1] >= u[x2]) {u[x2] += u[x1]; u[x1] = x2;} else {u[x1] += u[x2]; u[x2] = x1;}
}
int mkt(int l, int r)
{
int No = ++N;
if (l == r) {T[No].maxw = w0[l]; T[No].lch = T[No].rch = 0;} else {
int mid = l + r >> 1, l_r = mkt(l, mid), r_r = mkt(mid + 1, r);
T[No].maxw = T[T[No].lch = l_r].maxw >= T[T[No].rch = r_r].maxw ? T[l_r].maxw : T[r_r].maxw;
}
return No;
}
void prepare()
{
qsort(_E2, _m, sizeof(_E2[0]), cmp);
re(i, n) u[i] = -1;
int a, b, r1, r2, total = 0, maxsz, x, n0;
re(i, _m) {
a = _E2[i].a; b = _E2[i].b; r1 = UFS_find(a); r2 = UFS_find(b);
if (r1 != r2) {UFS_union(r1, r2); add_edge0(a, b, _E2[i].w); if (++total == n - 1) break;}
}
re(i, n) vst[i] = 0; Q[0] = DEP[0] = N = 0; vst[0] = 1; FA[0] = -1;
for (int front=0, rear=0; front<=rear; front++) {
a = Q[front];
for (int p=E0[a].next; p != a; p=E0[p].next) {
b = E0[p].b;
if (!vst[b]) {FA[b] = m; DEP[b] = DEP[a] + 1; vst[b] = 1; Q[++rear] = b; add_edge(a, b, E0[p].w);}
}
}
rre(i, n) {
a = Q[i]; SZ[a] = 1; maxsz = 0;
for (int p=E[a].next; p != a; p=E[p].next) {
b = E[p].b; SZ[a] += SZ[b]; if (SZ[b] > maxsz) {maxsz = SZ[b]; x = p;}
}
if (SZ[a] > 1) E[x].Z = 1;
}
UP[0] = ord[0] = 0;
re2(i, 1, n) {
a = Q[i]; int p = FA[a]; if (E[p].Z) {UP[a] = UP[E[p].a]; ord[a] = ord[E[p].a] + 1;} else {UP[a] = a; ord[a] = 0;}
if (SZ[a] == 1 && E[FA[a]].Z) {
b = UP[a]; n0 = ord[a]; for (int j=a; j!=b; j=E[FA[j]].a) w0[--n0] = E[FA[j]].w;
tot[b] = ord[a]; root[b] = mkt(0, ord[a] - 1);
for (int j=a; j!=b; j=E[FA[j]].a) {tot[j] = tot[b]; root[j] = root[b];}
}
}
}
int LCA(int a, int b)
{
while (1) {
if (UP[a] == UP[b]) return DEP[a] <= DEP[b] ? a : b;
else if (DEP[UP[a]] >= DEP[UP[b]]) a = E[FA[UP[a]]].a; else b = E[FA[UP[b]]].a;
}
}
void opr0(int l, int r, int No)
{
if (l >= l0 && r <= r0) {if (T[No].maxw > res) res = T[No].maxw;} else {
int mid = l + r >> 1;
if (mid >= l0) opr0(l, mid, T[No].lch);
if (mid < r0) opr0(mid + 1, r, T[No].rch);
}
}
int main()
{
int P, s, a0, b0, w0, LCA0, c;
scanf("%d%d%d", &n, &_m, &P); init_d();
re(i, _m) {
scanf("%d%d%d", &a0, &b0, &w0);
_E[i].a = _E2[i].a = --a0; _E[i].b = _E2[i].b = --b0; _E[i].w = _E2[i].w = w0;
}
prepare();
re(i, P) {
scanf("%d%d", &s, &w0); a0 = _E[--s].a; b0 = _E[s].b; LCA0 = LCA(a0, b0);
res = -INF;
while (DEP[a0] > DEP[LCA0]) {
if (E[FA[a0]].Z) {
if (DEP[UP[a0]] >= DEP[LCA0]) c = UP[a0]; else c = LCA0;
l0 = ord[c]; r0 = ord[a0] - 1; opr0(0, tot[a0] - 1, root[a0]); a0 = c;
} else {
if (E[FA[a0]].w > res) res = E[FA[a0]].w;
a0 = E[FA[a0]].a;
}
}
while (DEP[b0] > DEP[LCA0]) {
if (E[FA[b0]].Z) {
if (DEP[UP[b0]] >= DEP[LCA0]) c = UP[b0]; else c = LCA0;
l0 = ord[c]; r0 = ord[b0] - 1; opr0(0, tot[b0] - 1, root[b0]); b0 = c;
} else {
if (E[FA[b0]].w > res) res = E[FA[b0]].w;
b0 = E[FA[b0]].a;
}
}
puts(res >= w0 ? "Yes" : "No");
}
return 0;
}
好了，對于模板也就到此為止了，接下來該搞應(yīng)用了。