[置顶] 树链剖分小节

前段时间学习了下树链剖分，好久没看了，今天又复习一遍，赶紧写下来，别又忘了。

我们在信息学竞赛中，有时会碰到这么一类题型，在一棵树中，修改两点之间路径上的所有边（或点）上的某个变量（如边的长度，点的权值等等），然后询问单个点（或边）或者两点之间路径上的所有点（或边）的某些性质（如边权之和，最大边最小边等等）。对于这样的题，往往容易往线段树上去靠，但是，单单是用线段树是无法维护每一条链的性质的，所以我们需要一种算法将树链分开来，使得每条链可以和线段树中的一个区间一一对应上。(当然树链剖分远远不止这些简单的应用，也不一定要和线段树有什么关系，总之就是将树链剖分开来吧)。

树链剖分有很多种剖分方法，最常用的应该就是轻重边剖分了吧（在网上大部分介绍的都是这种剖分方法），什么是轻重边剖分呢？

我们首先将树中的边分为两部分，轻边和重边，记size(U)为以U为根的子树的节点的个数，令V为U的儿子中size最大的一个（如有多个最大，只取一个），则我们说边（U，V）为重边，其余的边为轻边（如下图所示红色为重边，蓝色为轻边）。

我们将一棵树的所有边按上述方法分成轻边和重边后，我们可以得到以下几个性质：

1：若（U,V）为轻边，则size(V)<=size(U)/2。

这是显然的。

2：从根到某一点的路径上轻边的个数不会超过O（logN），（N为节点总数）。

这也是很简单，因为假设从跟root到v的路径有k条轻边，它们是 root->...->v1->...->v2->......->vk->...->v，我们设size(v)=num，显然num>=1,则由性质1，我们有size(Vk)>=2,size(Vk-1)>=4......size(v1)>=2^k，显然有2^k<=N,所以k<=log2(N)。

如果我们把一条链中的连续重边连起来，成为重链，则一条链就变成了轻边与重链交替分段的链，且段数是log(N)级别的，则我们可以讲重链放在线段树中维护，轻边可放可不放，为了方便我一般还是放，但是速度就会打一点折扣了。思路就是这么多，接下来就是具体实现了。

我们需要维护一下值：

siz[v]表示以v为根的子树的节点总数。

dep[v]表示v的深度。

son[v]表示与v在同一重链上的v的儿子节点。

fa[v]表示v的父亲节点。

top[v]表示v所在链的顶端节点。

w[v]表示节点v在线段树中的位置。

siz[],son[],fa[],dep[]可以在第一遍dfs中求出来，top[]，w[]可在第二遍dfs中求出来。具体过程看代码吧。

struct edge
{
    int to;
    int next;
}e[maxn<<1];
int box[maxn],cnt,tot;
void init()
{
    tot=0;
    son[0]=dep[0]=0;
    memset(box,-1,sizeof(box));
    cnt=0;
}
void add(int from,int to)
{
    e[cnt].to=to;
    e[cnt].next=box[from];
    box[from]=cnt++;
}
int siz[maxn],top[maxn],son[maxn],dep[maxn],w[maxn],fa[maxn];
void dfs(int now,int pre)
{
    siz[now]=1;
    fa[now]=pre;
    son[now]=0;
    dep[now]=dep[pre]+1;
    int t,v;
    for(t=box[now];t+1;t=e[t].next)
    {
        v=e[t].to;
        if(v!=pre)
        {
            dfs(v,now);
            siz[now]+=siz[v];
            if(siz[son[now]]<siz[v])
            {
                son[now]=v;
            }
        }
    }
}
void dfs2(int now,int tp)
{
    w[now]=++tot;
    top[now]=tp;
    if(son[now])
    dfs2(son[now],top[now]);
    int t,v;
    for(t=box[now];t+1;t=e[t].next)
    {
        v=e[t].to;
        if(v!=fa[now]&&v!=son[now])
        dfs2(v,v);
    }
}

以上是剖分过程，关于如何在树链剖分后维护两点间路径的信息，请看这里LCA的树链剖分实现

这里需要注意的是，对于有些题要修改的权值或询问的权值在点上，有的在边上，这在剖分时虽然过程没有变，但在处理的时候是有区别的，具体不同我想在下面两道题里体现。

权值在边上的情况。

http://codeforces.com/problemset/problem/165/D

codeforces 165D Beard Graph

题意：给一棵树，树的每条边有一种颜色，黑色或白色，一开始所有边均为黑色，有两个 *** 作：

*** 作1：将第i条边变成白色或将第i条边变成黑色。

*** 作2 ：询问u，v两点之间仅经过黑色变的最短距离。

思路：其实这道题可以不用树链剖分，存在更高效的方法，但是一时又想不到更好的例子。

因为是一棵树，所以两点之间的路径是确定的，所以只需要判断路径中是否所有的边均为黑色边即可，全是黑边意味着没有白边，所以我们可以这么做，我们将每条边剖分放入线段树中后，初始时将所有边权设为0，对 *** 作1，如果要将一条边改为黑色，则将线段树赋值为零，否则分值为1，然后对于 *** 作2，我们只要看两点间路径是否权之和为0即可，若为0，返回两点间距离，否则返回0。

上代码：

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 100010
using namespace std;
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
struct tree
{
    int l,r;
    int sum;
}t[maxn<<2];
void pushup(int p)
{
    t[p].sum=t[ls].sum+t[rs].sum;
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r,t[p].sum=0;
    if(l==r)
    return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void add(int p,int x,int val)
{
    if(t[p].l==t[p].r)
    {
        t[p].sum+=val;
        return;
    }
    if(x<=mid)
    add(ls,x,val);
    else
    add(rs,x,val);
    pushup(p);
}
int query(int p,int l,int r)
{
    if(t[p].l==l&&t[p].r==r)
    {
        return t[p].sum;
    }
    if(l>mid)
    return query(rs,l,r);
    else if(r<=mid)
    return query(ls,l,r);
    else
    return query(ls,l,mid)+query(rs,mid+1,r);
}
int siz[maxn],top[maxn],son[maxn],dep[maxn],w[maxn],fa[maxn];
struct edge
{
    int to;
    int next;
}e[maxn<<1];
int box[maxn],cnt,tot;
void init()
{
    tot=0;
    son[0]=dep[0]=0;
    memset(box,-1,sizeof(box));
    cnt=0;
}
void add(int from,int to)
{
    e[cnt].to=to;
    e[cnt].next=box[from];
    box[from]=cnt++;
}
void dfs(int now,int pre)
{
    siz[now]=1;
    fa[now]=pre;
    son[now]=0;
    dep[now]=dep[pre]+1;
    int t,v;
    for(t=box[now];t+1;t=e[t].next)
    {
        v=e[t].to;
        if(v!=pre)
        {
            dfs(v,now);
            siz[now]+=siz[v];
            if(siz[son[now]]<siz[v])
            {
                son[now]=v;
            }
        }
    }
}
void dfs2(int now,int tp)
{
    w[now]=++tot;
    top[now]=tp;
    if(son[now])
    dfs2(son[now],top[now]);
    int t,v;
    for(t=box[now];t+1;t=e[t].next)
    {
        v=e[t].to;
        if(v!=fa[now]&&v!=son[now])
        dfs2(v,v);
    }
}
int solve(int a,int b)
{
    int f1=top[a],f2=top[b],dist=0;
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2])
        {
            swap(f1,f2);
            swap(a,b);
        }
        dist+=w[a]-w[f1]+1;
        int tmp=query(1,w[f1],w[a]);
        if(tmp)
        return -1;
        a=fa[f1];
        f1=top[a];
    }
    if(a==b)
    return dist;//注意这里
    else
    {
        if(dep[a]>dep[b])
        swap(a,b);
        int tmp=query(1,w[son[a]],w[b]);//注意这里
        if(tmp)
        return -1;
        return dist+w[b]-w[a];
    }
}
int Edge[maxn][2];
int main()
{
    int n,q,i,a,b;
    scanf("%d",&n);
    init();
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&Edge[i][0],&Edge[i][1]);
        add(Edge[i][0],Edge[i][1]);
        add(Edge[i][1],Edge[i][0]);
    }
    build(1,1,n);
    dfs(1,0);
    dfs2(1,1);
    scanf("%d",&q);
    while(q--)
    {
        int k;
        scanf("%d",&k);
        if(k==3)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",solve(a,b));
        }
        else
        {
            scanf("%d",&i);
            int tmp;
            if(dep[Edge[i][0]]>dep[Edge[i][1]])
            tmp=Edge[i][0];
            else
            tmp=Edge[i][1];
            if(k==1)
            add(1,w[tmp],-1);
            else
            add(1,w[tmp],1);
        }
    }
    return 0;
}

权值在点上的情况：

http://acm.hdu.edu.cn/showproblem.php?pid=3966

HDU:3966 Aragorn's Story

题意：题意很明白，给一棵树，将两点之间的路径中的所有点的权值增加或减少一个数，询问特定点当前的权值大小。

思路：思路应该很清晰了，将树剖分后放进线段树中维护。

代码如下：

#pragma comment(linker,"/STACK:100000000,100000000")
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 50010
using namespace std;
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
struct tree
{
    int l,r;
    int lazy;
}t[maxn<<2];
int siz[maxn],top[maxn],son[maxn],dep[maxn],w[maxn],fa[maxn],num[maxn],tt[maxn];
void pushdown(int p)
{
    if(t[p].lazy)
    {
        t[ls].lazy+=t[p].lazy;
        t[rs].lazy+=t[p].lazy;
        t[p].lazy=0;
    }
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r,t[p].lazy=0;
    if(l==r)
    {
        t[p].lazy=num[tt[l]];
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void add(int p,int l,int r,int val)
{
    if(t[p].l==l&&t[p].r==r)
    {
        t[p].lazy+=val;
        return;
    }
    pushdown(p);
    if(r<=mid)
    add(ls,l,r,val);
    else if(l>mid)
    add(rs,l,r,val);
    else
    {
        add(ls,l,mid,val);
        add(rs,mid+1,r,val);
    }
}
int query(int p,int x)
{
    if(t[p].l==t[p].r)
    {
        return t[p].lazy;
    }
    pushdown(p);
    if(x>mid)
    return query(rs,x);
    else
    return query(ls,x);
}
struct edge
{
    int to;
    int next;
}e[maxn<<1];
int box[maxn],cnt,tot;
void init()
{
    tot=0;
    son[0]=dep[0]=0;
    memset(box,-1,sizeof(box));
    cnt=0;
}
void add(int from,int to)
{
    e[cnt].to=to;
    e[cnt].next=box[from];
    box[from]=cnt++;
}
void dfs(int now,int pre)
{
    siz[now]=1;
    fa[now]=pre;
    son[now]=0;
    dep[now]=dep[pre]+1;
    int t,v;
    for(t=box[now];t+1;t=e[t].next)
    {
        v=e[t].to;
        if(v!=pre)
        {
            dfs(v,now);
            siz[now]+=siz[v];
            if(siz[son[now]]<siz[v])
            {
                son[now]=v;
            }
        }
    }
}
void dfs2(int now,int tp)
{
    w[now]=++tot;
    tt[tot]=now;
    top[now]=tp;
    if(son[now])
    dfs2(son[now],top[now]);
    int t,v;
    for(t=box[now];t+1;t=e[t].next)
    {
        v=e[t].to;
        if(v!=fa[now]&&v!=son[now])
        dfs2(v,v);
    }
}
void solve(int a,int b,int val)
{
    int f1=top[a],f2=top[b];
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2])
        {
            swap(f1,f2);
            swap(a,b);
        }
        add(1,w[f1],w[a],val);
        a=fa[f1];
        f1=top[a];
    }
    if(a==b)
    {
        add(1,w[a],w[a],val);//注意这里
    }
    else
    {
        if(dep[a]>dep[b])
        swap(a,b);
        add(1,w[a],w[b],val);//注意这里
    }
}
int main()
{
    freopen("dd.txt","r",stdin);
    int n,m,q,a,b,c;
    char str[2];
    while(scanf("%d%d%d",&n,&m,&q)!=EOF)
    {
        init();
        int i;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        dfs(1,0);
        dfs2(1,1);
        build(1,1,n);
        while(q--)
        {
            int node;
            scanf("%s",str);
            if(str[0]=='Q')
            {
                scanf("%d",&node);
                printf("%d\n",query(1,w[node]));
            }
            else
            {
                scanf("%d%d%d", &a,&b,&c);
                if(str[0]=='I')
                solve(a,b,c);
                else
                solve(a,b,-c);
            }
        }
    }
    return 0;
}

我已将需要注意的地方在代码中标记下来了，

区别就是在修改最后一条链时，也就是a,b在同一条重链中时，我们不妨设dep[a]<=dep[b]，这时我们知道a是原来我们要求的v,w两点的LCA。因为我们树链剖分时，将重链放入线段树中时，事实上将点与边一一对应了，每个点对应于其父节点与其连接的边，对于根节点，可设置一个虚拟节点，把它看成根节点的父节点。这样在放入线段树中的 *** 作就可以不变（其实还是为了实现方便）。如果权值在边上，那么我要求v,w两点间的路径时，其LCA所对应的边并不在这条路径里，所以我们要少更新一条边。如果权值在点上，则LCA显然也在v与w之间的路径中，则需要更新LCA。这就是两种题的不同点。

PS：其实树链剖分还有好多应用还有拓展，不过本弱菜还没有学得到，这里只是将最基本的应用总结出来，希望各位神牛不要BS。

PS2：DFS写法容易爆栈，所以还有非递归写法，如BFS写法和模拟栈等等，不过我还没研究出来。。。