原题地址
【有关树的路径剖分的东东在网上介绍的太多了……】
常见的路径剖分的方法是轻重边剖分,即把树中的边分为轻重两部分,方法:设SZ[i]为以i为根的子树的大小(结点总数),则若点x不是叶结点,则其子结点中SZ值最大的(注意,有多个SZ值最大的子结点应任选一个,只能选一个,防止出现重链相交,引发歧义)点y,边(x, y)称为重边,其余的边都是轻边。首尾相连的重边称为重链(注意一定是自上而下的),则一个很显然的性质是:从根结点到任意点i路径上的轻边与重链的总数都不会超过O(log2N)。然后,对每条重链上的边建立线段树,每当遇到改值操作,若是轻边就直接改,若是重边就在线段树里改;遇到找x、y路径上边权最大值的操作,只要找到LCA(x, y),然后从x、y开始沿着树边上溯到LCA(x, y)处,对于中间的每条轻边和重链(线段树内)导出最大值即可。

求LCA:可以对整棵树作深度优先遍历,记下每个遇到的点(包括向上的和向下的)的编号,形成一个长度为2(N-1)的序列A,然后,找到点x、y在A中的第一次出现的位置(设为FF[x]和FF[y]),则A[FF[x]..FF[y]]中的深度最小的点的编号就是LCA(x, y),显然这需要RMQ。

具体步骤:
(1)输入部分:建立无根树;
(2)预处理部分:分为6步:
<1>利用BFS将无根树转化为有根树,同时求出有根树中点i(根结点除外)到其父结点的边的编号(设为FA[i])以及点i的深度(设为DEP[i]);
<2>自底向上计算每个点的SZ值,同时划分轻重边(对于有根树中的每条边设立Z域,Z=1为重边,Z=0为轻边);
<3>求出重链,建立线段树:
求重链的方法:由于重链只会在叶结点处结束,因此从每个叶结点开始上溯,直到上溯到根或者遇到轻边为止。为了方便,需要对每个结点i记录以下4个值:UP[i]表示点i所在重链最顶上的那个结点的编号;ord[i]表示点i是其所在重链的上起第几个点(从0开始);tot[i]表示点i所在重链上有几个结点;root[i]表示点i所在重链建成的线段树的编号(这样经常写的opr(0, n-1, root)就可以表示成opr(0, tot[i]-1, root[i]))。求出重链以后,对沿途经历的所有边的权值倒序写入数组W0,再对数组W0建线段树即可。考虑到不同线段树的大小可能不同,这里采用压缩处理,这样就需要记录每个点的lch、rch编号(见代码);
<4>对树进行DFS遍历,求出序列A;
<5>求出序列A的倍增最小值,存放在A0[][]里(注意:A和A0中记载的都是编号,而判定大小的关键字是深度);
<6>求出LOG[i]=log2i(下取整);
(3)执行部分:对于询问操作,求LCA,不断上溯,对于重链在线段树里找即可,注意线段树的左右端点,尤其是当UP在LCA之上时,只能上溯到LCA处。

编程注意事项:建代码中标Attention的地方。
代码(我这个代码常数巨大,时间达3.61s,不知是肿么搞得,神犇来看一下啊囧):
#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 = 10001, MAXS = 20, INF = ~0U >> 2;
struct edge {
    
int a, b, w, pre, next;
    
bool Z;
} E0[MAXN 
<< 2], E[MAXN + MAXN + 1];
struct node {
    
int maxv, lch, rch;
} T[MAXN 
<< 2];
int n, m0, m, N, _a[MAXN], _b[MAXN], FA[MAXN], Q[MAXN], SZ[MAXN], DEP[MAXN], W0[MAXN], UP[MAXN], ord[MAXN], root[MAXN], tot[MAXN];
int n1, stk[MAXN], st[MAXN], A[MAXN << 2], A0[MAXN << 2][MAXS], FF[MAXN], LOG[MAXN << 2], l0, r0, x0, res;
bool vst[MAXN];
void init_d()
{
    re(i, n) E0[i].pre 
= E0[i].next = E[i].pre = 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 mkt(int l, int r)
{
    
int No = ++N;
    
if (l == r) {
        T[No].maxv 
= 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].lch = l_r; T[No].rch = r_r;
        
if (T[l_r].maxv >= T[r_r].maxv) T[No].maxv = T[l_r].maxv; else T[No].maxv = T[r_r].maxv;
    }
    
return No;
}
void prepare()
{
    re(i, n) vst[i] 
= 0; Q[0= 0; vst[0= 1; DEP[0= 0; FA[0= -1;
    
int i0, j0;
    
for (int front=0, rear=0; front<=rear; front++) {
        i0 
= Q[front];
        
for (int p=E0[i0].next; p != i0; p=E0[p].next) {
            j0 
= E0[p].b;
            
if (!vst[j0]) {add_edge(i0, j0, E0[p].w); vst[j0] = 1; Q[++rear] = j0; FA[j0] = m - 1; DEP[j0] = DEP[i0] + 1;}
        }
    }
    
int maxSZ, x, n0, root0;
    rre(i, n) {
        i0 
= Q[i]; SZ[i0] = 1; maxSZ = 0;
        
for (int p=E[i0].next; p != i0; p=E[p].next) {SZ[i0] += SZ[j0 = E[p].b]; if (SZ[j0] > maxSZ) {maxSZ = SZ[j0]; x = p;}}
        
if (SZ[i0] > 1) E[x].Z = 1;   //Attention
    }
    UP[
0= 0; ord[0= 0; N = 0;
    re2(i, 
1, n) {
        i0 
= Q[i]; x = FA[i0]; if (E[x].Z) {UP[i0] = UP[E[x].a]; ord[i0] = ord[E[x].a] + 1;} else {UP[i0] = i0; ord[i0] = 0;}
        
if (SZ[i0] == 1 && ord[i0]) {
            j0 
= UP[i0]; n0 = ord[i0];
            
for (int j=i0; j!=j0; j=E[FA[j]].a) {tot[j] = ord[i0]; W0[--n0] = E[FA[j]].w;} tot[j0] = ord[i0];  //Attention
            root0 = mkt(0, ord[i0] - 1);  //Attention
            for (int j=i0; j!=j0; j=E[FA[j]].a) root[j] = root0; root[j0] = root0;  //Attention
        }
    }
    re(i, n) {st[i] 
= E[i].next; FF[i] = -1;} stk[0= 0int tp = 0; n1 = 1; A[0= FF[0= 0;
    
while (tp >= 0) {
        i0 
= stk[tp]; x = st[i0];
        
if (x != i0) {
            j0 
= E[x].b; if (FF[j0] == -1) FF[j0] = n1; A[n1++= j0; st[i0] = E[x].next; stk[++tp] = j0;
        } 
else {
            
if (tp) A[n1++= stk[tp - 1];
            tp
--;
        }
    }
    rre(i, n1) {
        A0[i][
0= A[i]; x = 1;
        re2(j, 
1, MAXS) if (i + (x << 1<= n1) {
            
if (DEP[A0[i][j - 1]] <= DEP[A0[i + x][j - 1]]) A0[i][j] = A0[i][j - 1]; else A0[i][j] = A0[i + x][j - 1];  //Attention
            x <<= 1;
        } 
else break;
    }
    
int _x; x = 1;
    re(i, MAXS) {
        _x 
= x << 1;
        
if (_x < n1) re2(j, x, _x) LOG[j] = i; else {re2(j, x, n1) LOG[j] = i; break;}
        x 
= _x;
    }
}
void opr0(int l, int r, int No)
{
    
if (l == l0 && r == l0) T[No].maxv = x0; else {
        
int mid = l + r >> 1, lch = T[No].lch, rch = T[No].rch;
        
if (mid >= l0) opr0(l, mid, lch);
        
if (mid < l0) opr0(mid + 1, r, rch);
        
if (T[lch].maxv >= T[rch].maxv) T[No].maxv = T[lch].maxv; else T[No].maxv = T[rch].maxv;
    }
}
void opr1(int l, int r, int No)
{
    
if (l >= l0 && r <= r0) {
        
if (T[No].maxv > res) res = T[No].maxv;
    } 
else {
        
int mid = l + r >> 1;
        
if (mid >= l0) opr1(l, mid, T[No].lch);
        
if (mid < r0) opr1(mid + 1, r, T[No].rch);
    }
}
int main()
{
    
int tests, a0, b0, w0, LCA, LOG0, FF0, FF1, p0, tmp;
    
char ss[20], ch;
    scanf(
"%d"&tests);
    re(testno, tests) {
        scanf(
"%d"&n); init_d();
        re(i, n
-1) {scanf("%d%d%d"&a0, &b0, &w0); add_edge0(--a0, --b0, w0); _a[i] = a0; _b[i] = b0;}
        prepare(); ch 
= getchar();
        
while (1) {
            scanf(
"%s", ss);
            
if (!strcmp(ss, "QUERY")) {
                scanf(
"%d%d%*c"&a0, &b0); --a0; --b0;
                
if (a0 == b0) res = 0else res = -INF;
                FF0 
= FF[a0]; FF1 = FF[b0];
                
if (FF0 > FF1) {tmp = FF0; FF0 = FF1; FF1 = tmp;}
                LOG0 
= LOG[FF1 - FF0 + 1];
                
if (DEP[A0[FF0][LOG0]] <= DEP[A0[FF1 - (1 << LOG0) + 1][LOG0]]) LCA = A0[FF0][LOG0]; else LCA = A0[FF1 - (1 << LOG0) + 1][LOG0];
                
while (a0 != LCA) {
                    p0 
= FA[a0];
                    
if (E[p0].Z) {
                        r0 
= ord[a0] - 1if (DEP[UP[a0]] >= DEP[LCA]) l0 = 0else l0 = ord[LCA];  //Attention
                        if (l0 <= r0) opr1(0, tot[a0] - 1, root[a0]);  //Attention
                        if (l0) a0 = LCA; else a0 = UP[a0];
                    } 
else {
                        
if (E[p0].w > res) res = E[p0].w;
                        a0 
= E[p0].a;
                    }
                }
                
while (b0 != LCA) {
                    p0 
= FA[b0];
                    
if (E[p0].Z) {
                        r0 
= ord[b0] - 1if (DEP[UP[b0]] >= DEP[LCA]) l0 = 0else l0 = ord[LCA];  //Attention
                        if (l0 <= r0) opr1(0, tot[b0] - 1, root[b0]);  //Attention
                        if (l0) b0 = LCA; else b0 = UP[b0];
                    } 
else {
                        
if (E[p0].w > res) res = E[p0].w;
                        b0 
= E[p0].a;
                    }
                }
                printf(
"%d\n", res);
            } 
else if (!strcmp(ss, "CHANGE")) {
                scanf(
"%d%d"&a0, &w0); b0 = _b[--a0]; a0 = _a[a0];
                
if (FA[b0] == -1 || E[FA[b0]].a != a0) {tmp = a0; a0 = b0; b0 = tmp;}
                p0 
= FA[b0];
                
if (E[p0].Z) {
                    l0 
= ord[a0]; x0 = w0; opr0(0, tot[a0] - 1, root[a0]);
                } 
else E[p0].w = w0;
            } 
else break;
        }
    }
    
return 0;
}
树的路径剖分是解决树上路径的操作查询问题的有力工具,它还有一些更为强大的应用,以后再来搞……

Feedback

# re: QTREE——树的路径剖分(又称树链剖分)[未登录]  回复  更多评论   

2012-08-14 00:11 by 杨杨
对于修改操作,不一定需要使用LCA
直接贴别人的话:
http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html
修改操作:例如将u到v的路径上每条边的权值都加上某值x。
一般人需要先求LCA,然后慢慢修改u、v到公共祖先的边。而高手就不需要了。
记f1 = top[u],f2 = top[v]。
当f1 <> f2时:不妨设dep[f1] >= dep[f2],那么就更新u到f1的父边的权值(logn),并使u = fa[f1]。
当f1 = f2时:u与v在同一条重链上,若u与v不是同一点,就更新u到v路径上的边的权值(logn),否则修改完成;
重复上述过程,直到修改完成

比使用LCA快

# re: QTREE——树的路径剖分(又称树链剖分)  回复  更多评论   

2012-10-25 20:43 by Mato_No1
@杨杨
这个其实就是WJMZBMR自创的那种利用路径剖分求LCA的算法,见http://www.cppblog.com/MatoNo1/archive/2012/01/14/164163.html
只不过这个是在求LCA的过程中顺便操作了而已

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