树剖学习笔记1 树链剖分模板【树链剖分】【树】【线段树】
点击量:845
弄懂树剖这方面各个数组的定义,并熟练掌握线段树,树链剖分就不是难事。
我弄懂树链剖分是在教练的讲解和这篇文章的帮助下理解的,除了参考那篇文章,我再把重要的部分总结一下。
我们要弄懂几个概念,重孩子是一个节点所有孩子中子树节点数量最多的那一个,连接父节点和重孩子的边叫做重链,树链剖分实际上是一种优化,它将树上最重要的,也就是最常经过的几条链划为重点,用线段树来优化区间修改和查询。并且因为在一棵子树中dfs序是连续的,并且在任意一条重链上,dfs序也是连续的,那么我们认为轻链是单点修改,重链是区间修改,对于这种轻重分明的结构,时间复杂度是被优化在$ O(Nlog^2N)$的。
#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
int p;
int pnt[101000];
/***线段树开始***/
struct tnode
{
int l,r,v,lazy;
tnode(int l,int r,int v)
{
this->l=l;
this->r=r;
this->v=v;
lazy=0;
}
tnode(int l,int r)
{
this->l=l;
this->r=r;
lazy=0;
}
tnode()
{
lazy=0;
}
}t[432100];
int init[101000];
void build(int k,int l,int r)
{
if(l==r)
{
t[k]=tnode(l,r,init[pnt[l]]);
return;
}
t[k]=tnode(l,r);
build(ls,l,mid);
build(rs,mid+1,r);
t[k].v=(t[ls].v+t[rs].v)%p;
return;
}
void pushdown(int k)
{
t[k].v+=t[k].lazy*(t[k].r-t[k].l+1);
if(t[k].l!=t[k].r)
{
t[ls].lazy+=t[k].lazy;
t[rs].lazy+=t[k].lazy;
}
t[k].v%=p;
t[k].lazy=0;
return;
}
void change(int k,int l,int r,int x)
{
pushdown(k);
if(l==t[k].l&&r==t[k].r)
{
t[k].lazy+=x;
t[k].lazy%=p;
return;
}
t[k].v+=x*(r-l+1);
if(r<=Mid)
change(ls,l,r,x);
else if(l>Mid)
change(rs,l,r,x);
else
{
change(ls,l,Mid,x);
change(rs,Mid+1,r,x);
}
t[k].v%=p;
return;
}
int ask(int k,int l,int r)
{
pushdown(k);
if(t[k].l==l&&t[k].r==r)
return t[k].v%p;
if(r<=Mid)
return ask(ls,l,r);
else if(l>Mid)
return ask(rs,l,r);
else
return (ask(ls,l,Mid)+
ask(rs,Mid+1,r))%p;
}
/***线段树结束***/
/***链表+图开始***/
struct node
{
int n;
node *nxt;
node(int n)
{
this->n=n;
nxt=NULL;
}
node()
{
nxt=NULL;
}
};
node head[101000],*tail[101000];
/***链表+图结束***/
/***dfs***/
int w[101000],top[101000];
int fa[101000],hs[101000];//分别存父亲和重儿子
int dfn[101000],cnt=0,over[101000];
int d[101000];
void dfs(int x)
{
node *p=&head[x];
int maxw=0;
w[x]=1;
while(p->nxt!=NULL)
{
p=p->nxt;
if(p->n==fa[x])
continue;
fa[p->n]=x;
d[p->n]=d[x]+1;
dfs(p->n);
w[x]+=w[p->n];
if(w[p->n]>maxw)
{
maxw=w[p->n];
hs[x]=p->n;
}
}
return;
}
void Dfs(int x,int t)
{
dfn[x]=++cnt;
pnt[cnt]=x;
top[x]=t;
node *p=&head[x];
if(hs[x])
Dfs(hs[x],t);
while(p->nxt!=NULL)
{
p=p->nxt;
if(p->n==fa[x]||p->n==hs[x])
continue;
Dfs(p->n,p->n);
}
over[x]=cnt;
return;
}
/***dfs结束***/
/***路径修改与查询***/
void modifyp(int x,int y,int z)
{
int tx=d[top[x]],ty=d[top[y]];
while(top[x]!=top[y])
{
if(tx<ty)//表示topy要深一些
{
change(1,dfn[top[y]],dfn[y],z);//top[y]是小于等于y的dfn
y=top[y];
y=fa[y];
}
else
{
change(1,dfn[top[x]],dfn[x],z);
x=top[x];
x=fa[x];//两头不相交,不重复修改
}
tx=d[top[x]];
ty=d[top[y]];
}
if(dfn[x]<dfn[y])
{
int t=x;
x=y;
y=t;
}
change(1,dfn[y],dfn[x],z);
return;
}
int path(int x,int y)
{
int ans=0;
int tx=d[top[x]],ty=d[top[y]];
while(top[x]!=top[y])
{
if(tx<ty)
{
ans+=ask(1,dfn[top[y]],dfn[y]);
ans%=p;
y=top[y];
y=fa[y];
}
else
{
ans+=ask(1,dfn[top[x]],dfn[x]);
ans%=p;
x=top[x];
x=fa[x];
}
tx=d[top[x]];
ty=d[top[y]];
}
if(dfn[x]<dfn[y])
{
int t=x;
x=y;
y=t;
}
ans+=ask(1,dfn[y],dfn[x]);
return ans%p;
}
/***路径修改与查询结束***/
/***子树修改与查询***/
void modifyt(int x,int y)
{
change(1,dfn[x],over[x],y);
}
int tree(int x)
{
return ask(1,dfn[x],over[x])%p;
}
/***子树修改与查询结束***/
int main()
{
memset(hs,0,sizeof(hs));
int n,m,r,u,v,x,y,z;
scanf("%d%d%d%d",&n,&m,&r,&p);
for(int i=1;i<=n;i++)
{
tail[i]=&head[i];
scanf("%d",&init[i]);
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
tail[u]->nxt=new node(v);
tail[u]=tail[u]->nxt;
tail[v]->nxt=new node(u);
tail[v]=tail[v]->nxt;
}
fa[r]=0;
d[r]=1;
dfs(r);
Dfs(r,r);
build(1,1,n);
int opt;
for(int i=1;i<=m;i++)
{
scanf("%d",&opt);
switch(opt)
{
case 1:
scanf("%d%d%d",&x,&y,&z);
modifyp(x,y,z);
break;
case 2:
scanf("%d%d",&x,&y);
printf("%d\n",path(x,y));
break;
case 3:
scanf("%d%d",&x,&y);
modifyt(x,y);
break;
case 4:
scanf("%d",&x);
printf("%d\n",tree(x));
break;
}
}
return 0;
}
… [Trackback]
[…] Information to that Topic: wjyyy.top/421.html […]
… [Trackback]
[…] Info to that Topic: wjyyy.top/421.html […]
… [Trackback]
[…] Find More Info here to that Topic: wjyyy.top/421.html […]
… [Trackback]
[…] Read More Information here to that Topic: wjyyy.top/421.html […]