题目自己到洛谷上去看
题解
树链剖分模板题，以后再写详细的树链剖分（让我多做几道题）
先放代码，以后再补充详细的解释（留个坑）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 120000
#define MAXL MAX+MAX
#define lson (now<<1)
#define rson ((now<<1)|1)
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
struct Line
{
int v,next,w;
}e[MAXL];
int h[MAX],cnt=1;
int dep[MAX],hson[MAX],size[MAX],f[MAX],VV[MAX],V[MAX];
int top[MAX],idb[MAX],ide[MAX],tot,N,M,P,R,line[MAX];
struct Node
{
int val,lazy;
}c1[MAX*8];
inline void Add(int u,int v)
{
e[cnt]=(Line){v,h[u]};
h[u]=cnt++;
}
void DFS1(int u,int ff)
{
dep[u]=dep[ff]+1;//求深度
size[u]=1;//子树大小
hson[u]=0;//重儿子
f[u]=ff;//父亲
int v;
for(int i=h[u];i;i=e[i].next)
{
v=e[i].v;
if(v==ff)continue;
DFS1(v,u);
size[u]+=size[v];
if(size[v]>size[hson[u]])hson[u]=v;//求出重儿子
}
}
void DFS2(int u,int ff)
{
top[u]=ff;//重链顶端
idb[u]=++tot;//DFS序
line[tot]=u;
if(hson[u])DFS2(hson[u],ff);//强制先走重链
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==f[u]||v==hson[u])continue;
DFS2(v,v);//走轻链
}
ide[u]=tot;//子树结束位置
}
void pushdown1(int now,int l,int r)
{
c1[now].val=(c1[now].val+1LL*(r-l+1)*c1[now].lazy)%P;
c1[lson].lazy=(c1[lson].lazy+c1[now].lazy)%P;
c1[rson].lazy=(c1[rson].lazy+c1[now].lazy)%P;
c1[now].lazy=0;
}
void build1(int now,int l,int r)
{
if(l==r){c1[now].val=V[line[l]];return;}
int mid=(l+r)>>1;
build1(lson,l,mid);build1(rson,mid+1,r);
c1[now].val=(c1[lson].val+c1[rson].val)%P;
}
void update1(int now,int l,int r,int al,int ar,int w)
{
if(al==l&&ar==r){c1[now].lazy+=w;return;}
int mid=(l+r)>>1;
(c1[now].val+=1LL*(ar-al+1)*w)%=P;
if(ar<=mid)update1(lson,l,mid,al,ar,w);
else if(al>mid)update1(rson,mid+1,r,al,ar,w);
else {update1(lson,l,mid,al,mid,w);update1(rson,mid+1,r,mid+1,ar,w);}
}
int Query1(int now,int l,int r,int al,int ar)
{
pushdown1(now,l,r);
if(al==l&&ar==r)return c1[now].val%P;
int mid=(l+r)>>1;
if(ar<=mid)return Query1(lson,l,mid,al,ar);
if(al>mid)return Query1(rson,mid+1,r,al,ar);
return (Query1(lson,l,mid,al,mid)+Query1(rson,mid+1,r,mid+1,ar))%P;
}
void Change(int u,int v,int w)
{
int tp1=top[u],tp2=top[v];
while(tp1!=tp2)
{
if(dep[tp1]<dep[tp2])
{
swap(tp1,tp2);
swap(u,v);
}
update1(1,1,N,idb[tp1],idb[u],w);
u=f[tp1];
tp1=top[u];
}
if(dep[u]<dep[v])swap(u,v);
update1(1,1,N,idb[v],idb[u],w);
}
int Ask(int u,int v)
{
int tp1=top[u],tp2=top[v],re=0;
while(tp1!=tp2)
{
if(dep[tp1]<dep[tp2])
{
swap(tp1,tp2);
swap(u,v);
}
re=(re+Query1(1,1,N,idb[tp1],idb[u]))%P;
u=f[tp1];
tp1=top[u];
}
if(dep[u]<dep[v])swap(u,v);
return (re+Query1(1,1,N,idb[v],idb[u]))%P;
}
int main()
{
N=read();M=read();R=read();P=read();
for(int i=1;i<=N;++i)V[i]=read();
for(int i=1;i<N;++i)
{
int u=read(),v=read();
Add(u,v);Add(v,u);
}
DFS1(R,0);DFS2(R,R);
build1(1,1,N);
for(int i=1;i<=M;++i)
{
int kk=read();
if(kk==1)
{
int a=read(),b=read(),c=read();
Change(a,b,c);
}
if(kk==2)
{
int a=read(),b=read();
printf("%dn",Ask(a,b)%P);
}
if(kk==3)
{
int a=read(),b=read();
update1(1,1,N,idb[a],ide[a],b);
}
if(kk==4)
{
int a=read();
printf("%dn",Query1(1,1,N,idb[a],ide[a])%P);
}
}
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
