Rockdu's Blog

题目描述

如题，已知一棵包含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取模）

输入输出样例

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

2
21

说明

时空限制：1s，128M

数据规模：

对于30%的数据： $N\le 10,M\le 10$

对于70%的数据： N \leq {10}^3, M \leq {10}^3N≤10​3​​,M≤10​3​​

对于100%的数据： N \leq {10}^5, M \leq {10}^5N≤10​5​​,M≤10​5​​

（ 其实，纯随机生成的树LCA+暴力是能过的，可是，你觉得可能是纯随机的么233 ）

样例说明：

树的结构如下：

各个操作如下：

故输出应依次为2、21(重要的事情说三遍：记得取模)

用来练习线段树维护树链剖分的很好的模板题，要注意取模十分的慢，模的太暴力会TLE的。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int maxn=1e5+100;
struct edge{
    int v,next;
}e[maxn*2];
int cnt,idcnt;
int top[maxn],fa[maxn],nodew[maxn],d[maxn],tid[maxn],tidend[maxn],nrank[maxn],head[maxn],son[maxn],nbel[maxn];
LL n,m,mod,root;
void adde(int u,int v){
    e[cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt++;
}

void dfs1(int u,int p){
    d[u]=d[p]+1;
    fa[u]=p;
    nbel[u]=1;
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(v==p)    continue;
        dfs1(v,u);
        nbel[u]+=nbel[v];
        if(son[u]==-1 || nbel[v] > nbel[son[u]]){
            son[u]=v;
        }
    }
}

void dfs2(int u,int tp){
    tid[u]=++idcnt;
    nrank[idcnt]=u;
    top[u]=tp;
    if(son[u]==-1){
        tidend[u]=idcnt;
        return;
    }
    dfs2(son[u],tp);
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(v!=fa[u] && v!=son[u])
            dfs2(v,v);
    }
    tidend[u]=idcnt;
    return;
}

namespace Segtree{
    struct node{
        int l,r;
        LL sum,lazy;
    }tree[maxn<<2];
    void push_up(int rt){
        tree[rt].sum=(tree[rt*2].sum+tree[rt*2+1].sum)%mod;
    }
    void push_down(int rt){
        if(tree[rt].lazy){
            int l=tree[rt].l;
            int r=tree[rt].r;
            int mid=(l+r)/2;
            (tree[rt*2].sum+=((tree[rt].lazy)*((mid-l+1)))%mod)%=mod;
            (tree[rt*2+1].sum+=((tree[rt].lazy)*((r-mid)))%mod)%=mod;
            (tree[rt*2].lazy+=tree[rt].lazy)%=mod;
            (tree[rt*2+1].lazy+=tree[rt].lazy)%=mod;
            tree[rt].lazy=0;
        }
    }
    void build(int l,int r,int rt){
        tree[rt].l=l,tree[rt].r=r;
        if(l==r){
            tree[rt].sum=nodew[nrank[l]]*1LL;
            return;
        }
        int mid=(l+r)/2;
        build(l,mid,rt*2);
        build(mid+1,r,rt*2+1);
        push_up(rt);
    }
    void add(int l,int r,int rt,int dt){
        int tl=tree[rt].l,tr=tree[rt].r;
        if(l==tl && r==tr){
            (tree[rt].lazy+=(dt)*1LL)%=mod;
            (tree[rt].sum+=((((r-l+1))*(dt))%mod)*1LL)%=mod;
            return;
        }
        push_down(rt);
        int mid=(tl+tr)/2;
        if(r<=mid) add(l,r,rt*2,dt);
        else if(l>mid)    add(l,r,rt*2+1,dt);
        else add(l,mid,rt*2,dt),add(mid+1,r,rt*2+1,dt);
        push_up(rt);
    }
    LL query(int l,int r,int rt){
        int tl=tree[rt].l,tr=tree[rt].r;
        if(tl==l && tr==r)
            return tree[rt].sum%mod;
        push_down(rt);
        int mid=(tl+tr)/2;
        if(r<=mid)    return query(l,r,rt*2)%mod;
        else if(l>mid)    return query(l,r,rt*2+1)%mod;
        else return (query(l,mid,rt*2)+query(mid+1,r,rt*2+1))%mod;
    }
}

LL qsum(int a,int b){
    using namespace Segtree;
    LL ret=0;
    while(top[a]!=top[b]){
        if(d[top[a]]<d[top[b]])swap(a,b);
        (ret+=query(tid[top[a]],tid[a],1))%=mod;
        a=fa[top[a]];
    }
    if(d[a]<d[b])    swap(a,b);
    (ret+=query(tid[b],tid[a],1))%=mod;
    return ret;
}

void asum(int a,int b,int dt){
    using namespace Segtree;
    while(top[a]!=top[b]){
        if(d[top[a]]<d[top[b]])swap(a,b);
        add(tid[top[a]],tid[a],1,dt);
        a=fa[top[a]];
    }
    if(d[a]<d[b])    swap(a,b);
    add(tid[b],tid[a],1,dt);
}

void add_subtree(int u,int dt){
    Segtree::add(tid[u],tidend[u],1,dt);
}

LL q_subtree(int u){
    return Segtree::query(tid[u],tidend[u],1)%mod;
}

int main(){
    memset(head,-1,sizeof(head));
    memset(son,-1,sizeof(son));
    scanf("%lld%lld%lld%lld",&n,&m,&root,&mod);
    for(int i=1;i<=n;i++)
        scanf("%d",&nodew[i]);
    for(int i=1;i<=n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adde(u,v),adde(v,u);
    }
    dfs1(root,0);
    dfs2(root,root);
    Segtree::build(1,n,1);
    while(m--){
        int opt,a,b,c;
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d",&a,&b,&c);
            asum(a,b,c);
        }
        if(opt==2){
            scanf("%d%d",&a,&b);
            printf("%lld\n",qsum(a,b));
        }
        if(opt==3){
            scanf("%d%d",&a,&b);
            add_subtree(a,b);
        }
        if(opt==4){
            scanf("%d",&a);
            printf("%lld\n",q_subtree(a));
        }
    }
    return 0;
}