首页 > 代码库 > P3384 【模板】树链剖分

P3384 【模板】树链剖分

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 247 3 7 8 0 1 21 53 14 13 4 23 2 24 51 5 1 32 1 3
输出样例#1:
221

说明

时空限制: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|1using namespace std;const int N=1e5+10;const int M=N<<2;struct node{    int v,next;}e[N<<1];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]=1;    for(int i=head[x];i;i=e[i].next){        int v=e[i].v;        if(v!=f){            dfs(v,x,de+1);            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],1);    for(int i=head[x];i;i=e[i].next){        int v=e[i].v;        if(v!=fa[x]&&v!=son[x]){            getpos(v,0);        }    }}void build(int k,int l,int r){    if(l==r){        a[k]=val[dfn[l]];        return ;    }    int mid=l+r>>1;    build(lc,l,mid);    build(rc,mid+1,r);    a[k]=a[lc]+a[rc];}void pushdown(int k,int l,int r){    if(!tag[k]) return ;    int mid=l+r>>1;    a[lc]=(a[lc]+(mid-l+1)*tag[k])%mod;    a[rc]=(a[rc]+(r-mid)*tag[k])%mod;    tag[lc]+=tag[k];    tag[rc]+=tag[k];    tag[k]=0;}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+1)*w)%mod;        tag[k]+=w;        return ;    }    pushdown(k,l,r);    int mid=l+r>>1;    if(y<=mid) change(lc,l,mid,x,y,w);    else if(x>mid) change(rc,mid+1,r,x,y,w);    else change(lc,l,mid,x,mid,w),change(rc,mid+1,r,mid+1,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>>1;    if(y<=mid) return query(lc,l,mid,x,y);    else if(x>mid) return query(rc,mid+1,r,x,y);    else return (query(lc,l,mid,x,mid)+query(rc,mid+1,r,mid+1,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(1,1,n,id[top[x]],id[x],w);    }    if(dep[x]<dep[y]) swap(x,y);    change(1,1,n,id[y],id[x],w);}int findlist(int x,int y){    int ans=0;    for(;top[x]!=top[y];x=fa[top[x]]){        if(dep[top[x]]<dep[top[y]]) swap(x,y);        ans=(ans+query(1,1,n,id[top[x]],id[x]))%mod;    }    if(dep[x]<dep[y]) swap(x,y);    ans=(ans+query(1,1,n,id[y],id[x]))%mod;    return ans;} int main(){    scanf("%d%d%d%d",&n,&m,&rt,&mod);    for(int i=1;i<=n;i++) scanf("%d",&val[i]);    for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);    dfs(rt,rt,1);    getpos(rt,0);    build(1,1,n);    for(int i=1,opt,x,y,z;i<=m;i++){        scanf("%d",&opt);        if(opt==1){            scanf("%d%d%d",&x,&y,&z);            varylist(x,y,z);        }        else if(opt==2){            scanf("%d%d",&x,&y);            printf("%d\n",findlist(x,y));        }        else if(opt==3){            scanf("%d%d",&x,&z);            change(1,1,n,id[x],id[x]+siz[x]-1,z);        }        else if(opt==4){            scanf("%d",&x);            printf("%d\n",query(1,1,n,id[x],id[x]+siz[x]-1));        }    }    return 0;}

 

P3384 【模板】树链剖分