学习树链剖分有感

关于树链剖分

虽然这是个省选的知识点,但是其实不算特别难以理解。

最多花5小时的功夫就能理解,不过要是想写出来的话对于码力的门槛还是挺高的。

前置知识:线段树、LCA、dfs序 (请学完所有前置再来看本篇博客,LCA、线段树在博客中都有涉及)

知识重点:轻重链、对于重链的LCA、新添编号的连续性

思路

树链剖分解决的是:

  1. 将树从x到y结点最短路径上所有节点的值都加上z
  2. 求树从x到y结点最短路径上所有节点的值之和
  3. 将以x为根节点的子树内所有节点值都加上z
  4. 求以x为根节点的子树内所有节点值之和

变量申明

sum····················原编号下的点权
suma··················新编号下的点权
tree····················线段树中保存值
lazy····················懒惰标记(lazy标记)
f·························父节点
d························深度
siz······················子树大小
top·····················链顶编号
son····················重儿子编号
id·······················新编号
head,edge···········存图

重儿子

定义:x节点的重儿子是x节点的儿子中的子树大小最大的节点。

重儿子是在回溯的时候求的。首先DFS下去,上来的时候找到siz最大的儿子。

void dfs1(int now,int father,int depth){
    siz[now]=1;
    f[now]=father,d[now]=depth;
    int nxt;
    int maxson=0;
    for(int i=head[now];i;i=edge[i].nxt){
        nxt=edge[i].to;
        if(nxt!=father){
            dfs1(nxt,now,depth+1);
            siz[now]+=siz[nxt];
            if(siz[son[now]]<siz[nxt]){
                son[now]=nxt;
            }
        }
    }
}

第二次DFS

重链链顶

重链的链顶可以直接在DFS中传下来,如果当前是重儿子,则链顶还是传原来的。否则就更新链顶为当前节点。

新编号

新编号即DFS序,优先重儿子(这也是不直接在第一次DFS中处理的原因)。

关于为什么要优先重儿子:这样可以保证重链的编号是连续的,可以直接用线段树求得区间和。

新编号下的值

DFS是顺便做掉即可。

void dfs2(int now,int t){
    top[now]=t;
    id[now]=++cnt;
    suma[cnt]=sum[now];
    int nxt;
    if(!son[now])return ;//没有重儿子(即没有儿子)直接返回
    dfs2(son[now],t);
    for(int i=head[now];i;i=edge[i].nxt){
        nxt=edge[i].to;
        if(nxt!=f[now]&&nxt!=son[now]){
            dfs2(nxt,nxt);//注意这里是nxt,nxt
        }
    }
}

线段树

常规线段树,以新编号为编号处理数据。

LCA

顺着重链爬上去即可,与暴力LCA相仿。

void addlink(int x,int y,int s){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);//保证x深于y
        add(1,n,id[top[x]],id[x],1,s);//从链顶加到当前节点
        x=f[top[x]];//爬到链顶的父节点
    }
    if(d[x]>d[y])swap(x,y);//保证x浅于y(如果想深于的话下边add改一下即可)
    add(1,n,id[x],id[y],1,s);
    return ;
}
int anss;
void querylink(int x,int y){//同上
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        ans=0;
        query(1,n,id[top[x]],id[x],1);
        anss=(anss + ans) % p;
        x=f[top[x]];
    }
    if(d[x]>d[y])swap(x,y);
    ans=0;
    query(1,n,id[x],id[y],1);
    anss= (anss + ans) % p;
    return ;
}

最终代码

#include<bits/stdc++.h>
using namespace std;
int n,m,r,p;
int sum[100005];
int tot=0;
struct kkk{
    int nxt,to;
}edge[200005];
int head[100005];
void add_edge(int u,int v){
    tot++;
    edge[tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
int f[100005],d[100005],siz[100005],top[100005],son[100005],id[100005];
int suma[100005];
int cnt;
void dfs1(int now,int father,int depth){
    siz[now]=1;
    f[now]=father,d[now]=depth;
    int nxt;
    int maxson=0;
    for(int i=head[now];i;i=edge[i].nxt){
        nxt=edge[i].to;
        if(nxt!=father){
            dfs1(nxt,now,depth+1);
            siz[now]+=siz[nxt];
            if(siz[son[now]]<siz[nxt]){
                son[now]=nxt;
            }
        }
    }
}
void dfs2(int now,int t){
    top[now]=t;
    id[now]=++cnt;
    suma[cnt]=sum[now];
    int nxt;
    if(!son[now])return ;
    dfs2(son[now],t);
    for(int i=head[now];i;i=edge[i].nxt){
        nxt=edge[i].to;
        if(nxt!=f[now]&&nxt!=son[now]){
            dfs2(nxt,nxt);
        }
    }
}
long long tree[400005];
long long lazy[400005];
void down(int l,int r,int now){
    int mid = l + r >> 1;
    tree[now*2]= (tree[now*2] + (lazy[now]*(mid - l + 1)) % p) % p;
    tree[now*2+1]= (tree[now*2+1] + (lazy[now]*(r - mid)) % p) % p;
    lazy[now*2]= (lazy[now*2] + lazy[now]) % p;
    lazy[now*2+1]= (lazy[now*2+1] + lazy[now]) % p;
    lazy[now]=0;
}
void build(int l,int r,int now){
    if(l==r){
        tree[now]=suma[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,now*2);
    build(mid+1,r,now*2+1);
    tree[now]=(tree[now*2]+tree[now*2+1]) % p;
    return ;
}
void add(int l,int r,int goall,int goalr,int now,long long s){
    if(goall<=l&&r<=goalr){
        tree[now]= (tree[now] + s*(r-l+1)) % p;
        lazy[now]= (lazy[now] + s) % p;
        return ;
    }
    int mid=(l+r)/2;
    down(l,r,now);
    if(goall<=mid)add(l,mid,goall,goalr,now*2,s);
    if(goalr>mid)add(mid+1,r,goall,goalr,now*2+1,s);
    tree[now]=(tree[now*2]+tree[now*2+1]) % p;
    return ;
}
int ans;
void query(int l,int r,int goall,int goalr,int now){
    if(goall<=l&&r<=goalr){
        ans= (ans + tree[now]) % p;
        return ;
    }
    int mid=(l+r)/2;
    down(l,r,now);
    if(goall<=mid)query(l,mid,goall,goalr,now*2);
    if(mid<goalr)query(mid+1,r,goall,goalr,now*2+1);
    tree[now]=(tree[now*2]+tree[now*2+1]) % p; 
    return ;
}
void addlink(int x,int y,int s){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        add(1,n,id[top[x]],id[x],1,s);
        x=f[top[x]];
    }
    if(d[x]>d[y])swap(x,y);
    add(1,n,id[x],id[y],1,s);
    return ;
}
int anss;
void querylink(int x,int y){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        ans=0;
        query(1,n,id[top[x]],id[x],1);
        anss=(anss + ans) % p;
        x=f[top[x]];
    }
    if(d[x]>d[y])swap(x,y);
    ans=0;
    query(1,n,id[x],id[y],1);
    anss= (anss + ans) % p;
    return ;
}
int main(){
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++){
        cin>>sum[i]; 
    }
    int tx,ty;
    for(int i=0;i<n-1;i++){
        cin>>tx>>ty;
        add_edge(tx,ty);
        add_edge(ty,tx);
    }
    int xx,yy,zz,cc;
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,n,1);
    for(int i=0;i<m;i++){
        cin>>cc;
        if(cc==1){
            cin>>xx>>yy>>zz;
            addlink(xx,yy,zz%p);
        }else if(cc==2){
            cin>>xx>>yy;
            anss=0;
            querylink(xx,yy);
            cout<<anss<<endl;
        }else if(cc==3){
            cin>>xx>>zz;
            add(1,n,id[xx],id[xx]+siz[xx]-1,1,zz);
        }else{
            cin>>xx;
            ans=0;
            query(1,n,id[xx],id[xx]+siz[xx]-1,1);//id[xx]+siz[xx]即xx子树最后一个节点的新编号
            cout<<ans<<endl;
        }
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/641/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者