P3384 【模板】树链剖分
题目描述
如题,已知一棵包含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为根节点的子树内所有节点值之和
输入输出格式
输入格式:
第一行包含4个正整数N、M、R、P,分别表示树的结点个数、操作个数、根节点序号和取模数(即所有的输出结果均对此取模)。
接下来一行包含N个非负整数,分别依次表示各个节点上初始的数值。
接下来N-1行每行包含两个整数x、y,表示点x和点y之间连有一条边(保证无环且连通)
接下来M行每行包含若干个正整数,每行表示一个操作,格式如下:
操作1: 1 x y z
操作2: 2 x y
操作3: 3 x z
操作4: 4 x
输出格式:
输出包含若干行,分别依次表示每个操作2或操作4所得的结果(对P取模)
输入输出样例
输入样例#1:
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
输出样例#1:
2
21
说明
时空限制:1s,128M
数据规模:
对于30%的数据:N<=10,M<=10
对于70%的数据:N<=1000,M<=1000
对于100%的数据:N<=100000,M<=100000
(其实,纯随机生成的树LCA+暴力是能过的,可是,你觉得可能是纯随机的么233)
样例说明:
树的结构如下:
各个操作如下:
故输出应依次为2、21(重要的事情说三遍:记得取模)
弱弱的调了1个小时的树链剖分裸题
#include<cstdio>
#include<iostream>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const int N=1e5+;
const int M=N<<;
struct node{
int v,next;
}e[N<<];int tot,cnt;
int n,m,rt,mod,head[N],dep[N],top[N],siz[N],dfn[N],son[N],fa[N],id[N],val[N];
int a[M],tag[M];
void add(int x,int y){
e[++tot]=(node){y,head[x]};
head[x]=tot;
}
void dfs(int x,int f,int de){
fa[x]=f;dep[x]=de;siz[x]=;
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(v!=f){
dfs(v,x,de+);
siz[x]+=siz[v];
if(!son[x]||siz[son[x]]<siz[v]) son[x]=v;
}
}
}
void getpos(int x,bool hson){
if(hson) top[x]=top[fa[x]];
else top[x]=x;
id[x]=++cnt;
dfn[cnt]=x;
if(son[x]) getpos(son[x],);
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(v!=fa[x]&&v!=son[x]){
getpos(v,);
}
}
}
void build(int k,int l,int r){
if(l==r){
a[k]=val[dfn[l]];
return ;
}
int mid=l+r>>;
build(lc,l,mid);
build(rc,mid+,r);
a[k]=a[lc]+a[rc];
}
void pushdown(int k,int l,int r){
if(!tag[k]) return ;
int mid=l+r>>;
a[lc]=(a[lc]+(mid-l+)*tag[k])%mod;
a[rc]=(a[rc]+(r-mid)*tag[k])%mod;
tag[lc]+=tag[k];
tag[rc]+=tag[k];
tag[k]=;
}
void change(int k,int l,int r,int x,int y,int w){
if(l==x&&y==r){
a[k]=(a[k]+(r-l+)*w)%mod;
tag[k]+=w;
return ;
}
pushdown(k,l,r);
int mid=l+r>>;
if(y<=mid) change(lc,l,mid,x,y,w);
else if(x>mid) change(rc,mid+,r,x,y,w);
else change(lc,l,mid,x,mid,w),change(rc,mid+,r,mid+,y,w);
a[k]=a[lc]+a[rc];
}
int query(int k,int l,int r,int x,int y){
if(l==x&&r==y) return a[k]%mod;
pushdown(k,l,r);
int mid=l+r>>;
if(y<=mid) return query(lc,l,mid,x,y);
else if(x>mid) return query(rc,mid+,r,x,y);
else return (query(lc,l,mid,x,mid)+query(rc,mid+,r,mid+,y))%mod;
}
void varylist(int x,int y,int w){
for(;top[x]!=top[y];x=fa[top[x]]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(,,n,id[top[x]],id[x],w);
}
if(dep[x]<dep[y]) swap(x,y);
change(,,n,id[y],id[x],w);
}
int findlist(int x,int y){
int ans=;
for(;top[x]!=top[y];x=fa[top[x]]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+query(,,n,id[top[x]],id[x]))%mod;
}
if(dep[x]<dep[y]) swap(x,y);
ans=(ans+query(,,n,id[y],id[x]))%mod;
return ans;
}
int main(){
scanf("%d%d%d%d",&n,&m,&rt,&mod);
for(int i=;i<=n;i++) scanf("%d",&val[i]);
for(int i=,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(rt,rt,);
getpos(rt,);
build(,,n);
for(int i=,opt,x,y,z;i<=m;i++){
scanf("%d",&opt);
if(opt==){
scanf("%d%d%d",&x,&y,&z);
varylist(x,y,z);
}
else if(opt==){
scanf("%d%d",&x,&y);
printf("%d\n",findlist(x,y));
}
else if(opt==){
scanf("%d%d",&x,&z);
change(,,n,id[x],id[x]+siz[x]-,z);
}
else if(opt==){
scanf("%d",&x);
printf("%d\n",query(,,n,id[x],id[x]+siz[x]-));
}
}
return ;
}