树链剖分

xiaoxiao2021-02-28  12

        这几天跟lxn学了一下树链剖分(当然ljm小儿子是我的主讲老师啦,还是要感谢的),感觉挺简单的,怕忘在此记录一下。

        首先,如果不会线段树,先移步去学一下吧……好了现在我们很熟悉线段树,那么故事开始了:

        现在有个大佬走过来,命令你“在一棵树上进行路径的修改、求极值、求和”,你乍一听很高兴,上线段树(当然树状数组,SBT,splay都行啦。。。)!但操作起来你会发现,仅凭线段树是不能快速搞定它的。

        怎么办呢?一个貌似很高级的算法出现了,定睛一看,竟是树链剖分。(感觉好傻逼啊~~)

        所谓树链,就是树上的路径;剖分,就是把路径分为重链和轻链。

        什么是重链和轻链呢?假如现在我们定义 son[v] 表示以v为根的子树的节点数,depth[v] 表示v在树中的深度(根节点的深度为1),那么就有一下定义:

        定义科普:

                重儿子:son[u] 为v的子节点中son值最大的,那么u就是v的重儿子;

                轻儿子:v的其他子节点;

                重边:点v与其重儿子的连边;

                轻边:点v与其轻儿子的连边;

                重链:由重边连成的路径;

                轻链:轻边。

        由此我们若定义 top[v] 表示v所在的链的顶端节点,father[v] 表示v的父亲,heavy_son[v] 表示与v在同一重链上的v的儿子节点(你可以称其为重儿子),id[v] 表示v与其父亲节点的连边(你可以称其为v的父边)在线段树中的位置。只要把这些东西都求出来,就能用log(n) 的时间完成原问题中的操作了。

        一棵树如果被剖分了的话,会具有如下性质:

                性质一:如果 (v,u) 为轻边,则 son[u] * 2 < son[v] ;

                性质二:从根到某一节点的路径上轻链、重链的个数都不大于log(n) 。

        其实就是每经过一条轻边,点的个数就至少除以二。假如不理解,还是劝您先记住为好吧。

        有了这些定义和锐利的性质,我们就要开始实现算法了:

                一、求出father、depth、son、heavy_son、top、id

                我们采用两遍dfs 的方式将它们们求出:

                        dfs_1:把father、depth、son、heavy_son 求出来,这一步很简单,看看代码就能懂啦;

                        dfs_2:求出top 和id ;

         这一步怎么办呢?首先,对于v ,当heavy_son[v] 存在(即v不是叶子结点)时,显然,我们有top[heavy_son[v]] = top[v] 。线段树中,v的重边应当在v 的父边的后面,记做id[ heavy_son[v]] = totw + 1 , totw表示最后加入的一条边在线段树中的位置。此时为了使一条重链上的各边在线段树中连续分布,应当进行dfs_2(heavy_son[v])。其次,对于v 的各个轻儿子u ,显然有top[u] =u,并且id[u] = totw + 1,进行dfs_2 过程。这样就求出了top 和id ;

                将树中各边/点(依题而定)的权值在线段树中更新,建链和建线段树的过程就完成咯。

                二、修改操作

                eg. 将树从u到v节点最短路径上所有节点的权值加上dis;

                我想如果不用树链剖分,你可能会先求LCA,现在我们有了树剖,不妨这么办:

                记tu = top[u] ,tv = top[v] ,当tu <> tv 时,不妨设depth[tu] >= depth[tv] ,那么就更新 tu 到 u 点的权值,并使 u = father[tu] ,tu = top[u] ;当 tu = tv 时,u与v在同一条重链上,若u与v不是同一点,就更新u到v路径上的点的权值,否则修改完成。重复上述操作,直至修改完成。(具体代码里有)

                其他操作(如求极值,求和等)就类似啦!为了各位好理解,这里附上洛谷P3384的一道模板树链剖分代码:

#include <iostream>   #include <cstdio>   #include <cstring>   #include <algorithm>   #define hee for(int i=1;i<=n*2;i++) cout<<depth[i]<<' '; cout<<endl   using namespace std;   const int maxn=500005;   typedef long long LL;   int cnte,n,m,r,temp; LL mod;   int top[maxn],depth[maxn],father[maxn],id[maxn];   int head[maxn],son[maxn],heavy_son[maxn],a[maxn];   int real[maxn]; // real subscipt -> real[id[i]] == i   struct Edge{       int to,next;       }edge[maxn];   struct Segment_Tree{       LL l,r,sum,tag;   }tree[maxn];   inline int getint(void){       int x=0,f=1;       char ch=getchar();       for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;       for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';       return x*f;   }   inline LL getll(void){       LL x=0,f=1;       char ch=getchar();       for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;       for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';       return x*f;   }   inline void add_edge(const int&u,const int&v){       edge[++cnte].next=head[u];       edge[cnte].to=v;       head[u]=cnte;   }   void DFS_1(int now,int fa){       father[now]=fa;       depth[now]=depth[father[now]]+1;       son[now]=1;       for(int i=head[now];i;i=edge[i].next)           if(edge[i].to!=fa){               DFS_1(edge[i].to,now);               son[now]+=son[edge[i].to];               if(!heavy_son[now]||son[edge[i].to]>son[heavy_son[now]])                   heavy_son[now]=edge[i].to;           }   }   void DFS_2(int now,int first){       top[now]=first;       id[now]=++temp;       real[id[now]]=now;       if(!heavy_son[now]) return ;       DFS_2(heavy_son[now],first);       for(int i=head[now];i;i=edge[i].next)           if(edge[i].to!=heavy_son[now]&&edge[i].to!=father[now])               DFS_2(edge[i].to,edge[i].to);   }   inline void push_up(int now){       tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;   }   inline void push_down(int now){       tree[now<<1].tag+=tree[now].tag;       tree[now<<1].sum+=tree[now].tag*(tree[now<<1].r-tree[now<<1].l+1);       tree[now<<1|1].tag+=tree[now].tag;       tree[now<<1|1].sum+=tree[now].tag*(tree[now<<1|1].r-tree[now<<1|1].l+1);       tree[now].tag=0;   }   void build(int now,int l,int r){       tree[now].l=l;       tree[now].r=r;       if(l==r){ tree[now].sum=a[real[l]]; return ; }       int mid=(tree[now].l+tree[now].r)>>1;       build(now<<1,l,mid);       build(now<<1|1,mid+1,r);       push_up(now);   }   void update(int now,int ll,int rr,LL x){       if(ll<=tree[now].l&&tree[now].r<=rr){           tree[now].tag+=x;           tree[now].sum+=x*(tree[now].r-tree[now].l+1);           return ;       }       push_down(now);       int mid=(tree[now].l+tree[now].r)>>1;       if(rr<=mid) update(now<<1,ll,rr,x);       else if(ll>mid) update(now<<1|1,ll,rr,x);       else{           update(now<<1,ll,mid,x);           update(now<<1|1,mid+1,rr,x);       }       push_up(now);   }   LL query_sum(int now,int ll,int rr){       if(ll<=tree[now].l&&tree[now].r<=rr) return tree[now].sum;       push_down(now);       int mid=(tree[now].l+tree[now].r)>>1;       if(rr<=mid) return query_sum(now<<1,ll,rr);       else if(ll>mid) return query_sum(now<<1|1,ll,rr);       else return query_sum(now<<1,ll,mid)+query_sum(now<<1|1,mid+1,rr);   }   void change(int u,int v,LL x){       int tu=top[u],tv=top[v];       while(tu!=tv){           if(depth[tu]<depth[tv]){ swap(tu,tv); swap(u,v); }           update(1,id[tu],id[u],x); u=father[tu]; tu=top[u];       }       if(depth[u]>depth[v]) swap(u,v);       update(1,id[u],id[v],x);   }   int find_sum(int u,int v){       LL sum=0; int tu=top[u],tv=top[v];       while(tu!=tv){           if(depth[tu]<depth[tv]){ swap(tu,tv); swap(u,v); }           sum+=query_sum(1,id[tu],id[u]); sum%=mod;           u=father[tu]; tu=top[u];       }       if(depth[u]>depth[v]) swap(u,v); sum+=query_sum(1,id[u],id[v]);       return sum%=mod;   }   void root_add(int now,LL x){       int begin=id[now];       int end=id[now]+son[now]-1;       update(1,begin,end,x);   }   LL root_sum(int now){       int begin=id[now];       int end=id[now]+son[now]-1;       return query_sum(1,begin,end)%mod;   }   int main(int argc,char const*argv[]){       n=getint(); m=getint(); r=getint(); mod=getll();       for(int i=1;i<=n;i++) a[i]=getint();       for(int i=1;i<=n-1;i++){           int u=getint(),v=getint();           add_edge(u,v); add_edge(v,u);       }       DFS_1(r,0); DFS_2(r,r); build(1,1,temp);       for(int i=0;i<m;i++){           int t=getint(),x,y,z;           if(t==1){ x=getint(),y=getint(),z=getint(); change(x,y,z); }           else if(t==2){ x=getint(),y=getint(); printf("%lld\n",find_sum(x,y)); }           else if(t==3){ x=getint(),y=getint(); root_add(x,y); }           else if(t==4){ x=getint(); printf("%lld\n",root_sum(x)); }           //hee;       }       return 0;   }  

        总之树剖就是这么简单啦,还有一些题,如树的统计(洛谷)等模板题,各位自己去刷吧。最后还是要谢谢ljm儿子的亲情讲解,看来还是养个儿用处多啊!
转载请注明原文地址: https://www.6miu.com/read-250300.html

最新回复(0)