树链剖分 - Luogu 3384【模板】树链剖分

【模板】树链剖分

题目描述

已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:

操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z

操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和

操作3: 格式: 3 x z 表示将以x为根节点的子树内所有节点值都加上z

操作4: 格式: 4 x 表示求以x为根节点的子树内所有节点值之和


树链剖分模板题废话

然而事实上我之前一直都不会树链剖分(真不知道我怎么活到现在的)

听说树链剖分有维护一棵线段树和多棵的版本

但是这里因为要维护子树其实是懒得写另一种,用两遍dfs的一棵线段树版本

先明确一下概念

重儿子:点v的子节点中sz值最大的儿子。

轻儿子:v的其它子节点。

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

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

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

轻链:有轻边的路径。

树链剖分概述

树链,就是树上的路径。

剖分,就是把路径分类为重链和轻链。

记sz[v]表示以v为根的子树的节点数,

dep[v]表示v的深度,

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

fa[v]表示v的父亲,

mxch表示与v在同一重链上的v的儿子节点,

loc[v]表示v与其父亲节点的连边在线段树中的位置。

只要把这些东西求出来,就能用logn的时间完成原问题中的操作。

剖分后的树有如下性质:

  1. 如果(v,u)为轻边,则siz[u] * 2 < siz[v];
  2. 从根到某一点的路径上轻链、重链的个数都不大于logn。

实现

这里我们用两遍大法师的一棵线段树版本

  1. 第一次,把sz,fa,mxch,dep求出来。在场的我相信你们都知道怎么写,实在不行复习一下树的遍历
  2. 第二次,对于每个节点v,

    2.1. 当v不是叶子节点,有top[mxch] = top[v]。

    线段树中,v的重边应当在v的父边的后面,记loc[mxch] = las+1,las表示到现在为止最后加入的一条边在线段树中的位置。

    此时,为了使一条重链各边在线段树中连续分布,应当进行DFS2(mxch);

    2.2. 对于v的各个轻儿子u,显然有top[u] = u,并且loc[u] = las+1,DFS2它。

之后将树中各边的权值sei进线段树,建树链和建线段树的过程就完成了。

想了解更多,去GZY大佬推荐的博客 http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html .


代码蒯上

可能因为博主咸鱼,有些地方看起来不和谐,请谅解。

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
inline int gotcha()
{
register int _a=0;bool _b=1;register char _c=getchar();
while(_c<'0' || _c>'9'){if(_c=='-')_b=0;_c=getchar();}
while(_c>='0' && _c<='9')_a=_a*10+_c-48,_c=getchar();
return _b?_a:-_a;
}
const int _ = 200002;
struct tree{int l,r,v,lzy;}tr[4*_];
struct edge{int to,ne;edge(){to=ne=0;}}eg[2*_];
int he[_]={0},io[_]={0},ecnt=0;
void add(int fr,int to)
{io[fr]++;eg[++ecnt].to=to;eg[ecnt].ne=he[fr];he[fr]=ecnt;}
int w[_],num[_],e[_],top[_],rnk[_],sz[_],dep[_],fa[_],n,m,mo,s,tot,z;
void plant(int d,int l,int r)
{
int mid=(l+r)>>1;
tr[d].l=l,tr[d].r=r;
if(l==r)return;
plant(d<<1,l,mid),plant(d<<1|1,mid+1,r);
}
void down(int d)
{
if(!tr[d].lzy)return;
tr[d].v+=tr[d].lzy*(tr[d].r-tr[d].l+1)%mo;
tr[d<<1].lzy+=tr[d].lzy;tr[d<<1|1].lzy+=tr[d].lzy;
tr[d].lzy=0;
}
void change(int d,int l,int r,int add)
{
if(tr[d].l>r||tr[d].r<l)return;
if(tr[d].l>=l && tr[d].r<=r){tr[d].lzy+=add,down(d);return;}
change(d<<1,l,r,add),change(d<<1|1,l,r,add),down(d<<1),down(d<<1|1);
tr[d].v=(tr[d<<1].v+tr[d<<1|1].v)%mo;
}
int finder(int d,int l,int r)
{
if(tr[d].l>r||tr[d].r<l)return 0;
if(tr[d].l>=l && tr[d].r<=r)return (tr[d].v)%mo;
down(d<<1);down(d<<1|1);
return (finder(d<<1,l,r)+finder(d<<1|1,l,r))%mo;
}
void inv_change(int x,int y,int add)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
change(1,num[top[x]],num[x],add);
x=fa[top[x]];
}
if(num[x]>num[y])swap(x,y);change(1,num[x],num[y],add);
}
int sp_finder(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
(ans+=finder(1,num[top[x]],num[x]))%=mo;
x=fa[top[x]];
}
if(num[x]>num[y])swap(x,y);
(ans+=finder(1,num[x],num[y]))%=mo;
return ans;
}
void DFS(int d,int faa)
{
int i=0;sz[d]=1;dep[d]=dep[faa]+1;
fa[d]=faa;
for(i=he[d];i;i=eg[i].ne)
if(eg[i].to!=faa)DFS(eg[i].to,d),sz[d]+=sz[eg[i].to];
}
void DFS2(int d,int head)
{
int i,mxch=0;
top[d]=head;num[d]=++tot;rnk[num[d]]=tot;change(1,tot,tot,w[d]);
if(io[d]==1 && d!=s){e[d]=d;return;}
for(i=he[d];i;i=eg[i].ne)
if(sz[eg[i].to]<sz[d] && sz[eg[i].to]>sz[mxch])mxch=eg[i].to;
DFS2(mxch,head);e[d]=e[mxch];
for(i=he[d];i;i=eg[i].ne)
if(sz[eg[i].to]<sz[d] && eg[i].to!=mxch)
DFS2(eg[i].to,eg[i].to),e[d]=e[eg[i].to];
}
int main()
{
register int i,op,a,b,c;
n=gotcha(),m=gotcha(),s=gotcha(),mo=gotcha();
for(i=1;i<=n;i++)w[i]=gotcha();
for(i=1;i<=n-1;i++)a=gotcha(),b=gotcha(),add(a,b),add(b,a);
plant(1,1,n),DFS(s,0),DFS2(s,s);
for(i=1;i<=m;i++)
{
op=gotcha(),a=gotcha();
if(op==1)b=gotcha(),c=gotcha(),inv_change(a,b,c);
else if(op==2)b=gotcha(),printf("%d\n",sp_finder(a,b)%mo);
else if(op==3)b=gotcha(),change(1,num[a],num[e[a]],b);
else printf("%d\n",finder(1,num[a],num[e[a]])%mo);
}
return 0;
}
上一篇:刷题总结——骑士的旅行(bzoj4336 树链剖分套权值线段树)


下一篇:DLLHijack漏洞原理