[置顶] 树链剖分小节

[置顶] 树链剖分小节,第1张

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

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

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

我们首先将树中的边分为两部分,轻边和重边,记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写法和模拟栈等等,不过我还没研究出来。。。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/2090317.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-07-22
下一篇 2022-07-22

发表评论

登录后才能评论

评论列表(0条)

保存