【1】新型LCA算法:(在WJMZBMR神犇空间上发现的,系神犇自创,Orz!!!)
这种算法可以在仅使用树的路径剖分预处理中求出的DEP和UP来求任意两点的LCA,时间复杂度为O(log2N),不需要单独的预处理。
步骤(假设求a0、b0两点的LCA):
(1)若UP[a0]==UP[b0],则a0、b0位于同一条重链上,显然a0、b0中深度小的那个就是LCA了,返回结果,结束;
(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所在的重链上必然存在一个点C,满足DEP[C]=DEP[UP[a0]],显然,C也是b0的祖先,这就说明在树中同一深度处存在两个不同的结点,它们都是b0的祖先,这是不可能的,所以,LCA不可能在a0所在重链上。那么,a0就可以上溯到UP[a0]的父结点处(也就是E[FA[UP[a0]]].a),b0不动,然后继续判断;
(3)若UP[a0]!=UP[b0]且DEP[UP[a0]]<DEP[UP[b0]],则LCA不可能在b0所在的重链上,将b0上溯到E[FA[UP[b0]]].a,a0不动,继续判断。
由于a0、b0最多上溯O(log2N)次,所以该算法一定能在O(log2N)时间内求出LCA(a0, b0)。
该算法的应用很广,不光可以在树的路径剖分中快速求出LCA,精简代码,同时也减少了一些时间(因为它不需要像RMQ那样进行预处理),而且,在一般的求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】树的路径剖分模板总结:
(1)预处理部分:由于采用新型LCA算法(注意,求LCA的过程写成专门的函数),所以,原来预处理部分的后3步都不需要了,也就是只要前3步:第一步建有根树求出FA、DEP;第二步求出SZ划分轻重边;第三步找重链建线段树求出UP、ord、tot和root。那些为了求RMQ而设置的数组也不需要了。
(2)操作部分:难点在于上溯过程和衔接。设待操作的路径为a0->b0(注意是有向的,无向的也可以当成有向的处理),LCA0=LCA(a0, b0);
对于点权型的树,a0->LCA0的过程需要包含LCA0,而b0->LCA0的过程不能包含LCA0。因此当b0==LCA0时,第二步应该什么事都不做,所以要特判;此外,如果N==1(树中只有一个结点),为了防止引用根的父结点,也需要直接特判掉,所以,上溯过程可以分以下4步:
<1>特判:若n=1(此时必然有a0==b0==0),直接操作0号结点,结束;
<2>(a0->LCA)若a0是父边是轻边的叶结点,则单独处理a0,最新点设为a0,a0跳到a0的父结点处开始,否则从a0开始(上溯)。上溯终止条件为DEP[a0]<DEP[LCA0]或者上溯到根结点,每次处理时,设c=”UP[a0]不超越LCA?UP[a0]:LCA",对[c, a0]段处理(l0=ord[c], r0=ord[a0]),再将a0上溯到c的父结点处(若c是根结点则退出);处理时,线段树中记录的所有有向的(从左到右的)信息都要反向;衔接时应不断向右衔接;
<3>(b0->LCA)与<2>类似,两个不同点:一是有向的信息不要反向,衔接时应不断向左衔接;二是若c==LCA,则l0=ord[c]+1;
<4>最后将<2>中和<3>中得到的两个衔接链再衔接一下即可;

对于边权型的树,a0->LCA0的过程和b0->LCA0的过程都要包含LCA0引出的边,b0==LCA0以及N==1时不需要特判(因为它们会自动地什么事都不做);在处理过程中,l0=ord[c], r0=ord[a0]-1;要分轻边和重链分别处理;每次a0上溯到c而不是c的父结点处;终止条件为DEP[a0]<=DEP[LCA0]。

模板题:PKU2831(动态最小生成树问题,需要涉及到最小生成树中两点之间路径上的最大边权,用树的路径剖分。其实本题有离线算法,不需要树的路径剖分)
#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)->- ((_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 - 1break;}
    }
    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;
}

好了,对于模板也就到此为止了,接下来该搞应用了。

Feedback

# re: 新型LCA算法及树的路径剖分模板总结  回复  更多评论   

2012-02-19 22:27 by Neroysq
讲得很有条理清晰易懂啊
顶一个!

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理