「模板」 树链剖分 HLD
<题目链接>
#include <algorithm>
#include <cstdio>
#include <cstring>
using std::swap;
const int MAXN=100010,MAXM=200010;
int n,m,rt,P;
class HLD
{
public:
HLD(void)
{
num=cnt=0;
memset(vis,0,sizeof vis);
memset(head,0,sizeof head);
memset(p,0,sizeof p);
}
void Init(void)
{
for(int i=1;i<=n;++i)
scanf("%d",&p[i].v);
for(int i=1,x,y;i<n;++i)
{
scanf("%d %d",&x,&y);
AddEdges(x,y);
}
DFS1(rt,1),DFS2(rt,rt),T.Build(this,1,1,n);
}
void AddPath(int x,int y,int v)
{
int a,b;
while((a=p[x].top)^(b=p[y].top))
p[a].d>p[b].d ? (T.Add(1,p[a].DFN,p[x].DFN,v),x=p[a].ft) : (T.Add(1,p[b].DFN,p[y].DFN,v),y=p[b].ft);
if(p[x].d>p[y].d)
swap(x,y);
T.Add(1,p[x].DFN,p[y].DFN,v);
}
int SumPath(int x,int y)
{
int a,b,ans=0;
while((a=p[x].top)^(b=p[y].top))
p[a].d>p[b].d ? (ans+=T.Sum(1,p[a].DFN,p[x].DFN),x=p[a].ft) : (ans+=T.Sum(1,p[b].DFN,p[y].DFN),y=p[b].ft);
if(p[x].d>p[y].d)
swap(x,y);
return (ans+T.Sum(1,p[x].DFN,p[y].DFN))%P;
}
void AddSubtree(int x,int v)
{
T.Add(1,p[x].DFN,p[x].DFN+p[x].size-1,v);
}
int SumSubtree(int x)
{
return T.Sum(1,p[x].DFN,p[x].DFN+p[x].size-1);
}
private:
bool vis[MAXN];
int cnt,num,head[MAXN],rank[MAXN];
struct node
{
int v,d,ft,son,size,top,DFN;
}p[MAXN];
struct edge
{
int nxt,to;
edge(int _nxt=0,int _to=0)
{
nxt=_nxt,to=_to;
}
}e[MAXM];
class SegmentTree
{
public:
void Build(HLD *qwq,int i,int l,int r)
{
s[i]=node(l,r,0);
if(l==r)
{
s[i].v=qwq->p[qwq->rank[l]].v;
return;
}
int j=i<<1,mid=l+r>>1;
Build(qwq,j,l,mid),Build(qwq,j|1,mid+1,r);
PushUp(i);
}
void Add(int i,int l,int r,int v)
{
if(l==s[i].l && r==s[i].r)
{
Update(i,v);
return;
}
if(s[i].l^s[i].r && s[i].lazy)
PushDown(i);
int j=i<<1,mid=s[i].l+s[i].r>>1;
if(r<=mid)
Add(j,l,r,v);
else if(l>mid)
Add(j|1,l,r,v);
else
Add(j,l,mid,v),Add(j|1,mid+1,r,v);
PushUp(i);
}
int Sum(int i,int l,int r)
{
if(l==s[i].l && r==s[i].r)
return s[i].v;
if(s[i].l^s[i].r && s[i].lazy)
PushDown(i);
int j=i<<1,mid=s[i].l+s[i].r>>1;
if(r<=mid)
return Sum(j,l,r);
else if(l>mid)
return Sum(j|1,l,r);
else
return (Sum(j,l,mid)+Sum(j|1,mid+1,r))%P;
}
private:
struct node
{
int l,r,v,lazy;
node(int _l=0,int _r=0,int _lazy=0)
{
l=_l,r=_r,lazy=_lazy;
}
}s[MAXN<<2];
void Update(int i,int v)
{
s[i].v=(s[i].v+v*(s[i].r-s[i].l+1))%P;
s[i].lazy=(s[i].lazy+v)%P;
}
void PushUp(int i)
{
int j=i<<1;
s[i].v=(s[j].v+s[j|1].v)%P;
}
void PushDown(int i)
{
int j=i<<1;
Update(j,s[i].lazy),Update(j|1,s[i].lazy);
s[i].lazy=0;
}
}T;
void AddEdge(int u,int v)
{
e[++cnt]=edge(head[u],v);
head[u]=cnt;
}
void AddEdges(int u,int v)
{
AddEdge(u,v),AddEdge(v,u);
}
void DFS1(int u,int k)
{
p[u].d=k,p[u].size=1;
for(int i=head[u],v;i;i=e[i].nxt)
if(!p[v=e[i].to].size)
{
DFS1(v,k+1);
p[v].ft=u,p[u].size+=p[v].size;
if(p[v].size>p[p[u].son].size)
p[u].son=v;
}
}
void DFS2(int u,int top)
{
p[u].top=top,vis[u]=1;
p[u].DFN=++num,rank[num]=u;
if(p[u].son)
DFS2(p[u].son,top);
for(int i=head[u],v;i;i=e[i].nxt)
if(!vis[v=e[i].to])
DFS2(v,v);
}
}HLT;
int main(int argc,char *argv[])
{
scanf("%d %d %d %d",&n,&m,&rt,&P);
HLT.Init();
for(int i=1,opt,x,y,z;i<=m;++i)
{
scanf("%d %d",&opt,&x);
switch(opt)
{
case 1:
scanf("%d %d",&y,&z);
HLT.AddPath(x,y,z);
break;
case 2:
scanf("%d",&y);
printf("%d\n",HLT.SumPath(x,y));
break;
case 3:
scanf("%d",&z);
HLT.AddSubtree(x,z);
break;
case 4:
printf("%d\n",HLT.SumSubtree(x));
break;
}
}
return 0;
}