x 树上求和

川长思鸟来 2022-09-04 10:58 117阅读 0赞

树上求和 https://ac.nowcoder.com/acm/problem/19428
        
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    const int MOD=23333;
    #define ll long long
    struct sgt_tree
    {
        #define ls (x<<1)
        #define rs (x<<1|1)
        ll lz[maxn*20],s1[maxn*20],s2[maxn*20];
        ll val[maxn];
        ll mul(ll a,ll b)
        {
            return ((a%MOD)*(b%MOD))%MOD;
        }
        ll mul(ll a,ll b,ll c)
        {
            return mul(a,b)*c%MOD;
        }
        void pushup(int x)
        {
            s1[x]=(s1[ls]+s1[rs])%MOD;
            s2[x]=(s2[ls]+s2[rs])%MOD;
        }
        void build(int x,int l,int r)
        {
    
    
            if(l==r)
            {
                s1[x]=val[l]%MOD;
                s2[x]=(s1[x]*s1[x])%MOD;
                return;
            }
            int mid=(l+r)>>1;
            build(ls,l,mid);
            build(rs,mid+1,r);
            pushup(x);
        }
        void pushdown(int x,int l,int r)
        {
            if(!lz[x])return;
            int mid=(l+r)>>1;
            lz[ls]=(lz[ls]+lz[x])%MOD;
            lz[rs]=(lz[rs]+lz[x])%MOD;
            s2[ls]=s2[ls]+mul(mid-l+1,lz[x],lz[x])+mul(s1[ls],2*lz[x])%MOD;
            s2[rs]=s2[rs]+mul(r-mid,lz[x],lz[x])+mul(s1[rs],2*lz[x])%MOD;
            s1[ls]=(s1[ls]+mul(mid-l+1,lz[x]))%MOD;
            s1[rs]=(s1[rs]+mul(r-mid,lz[x]))%MOD;
            lz[x]=0;
        }
        ll query(int x,int l,int r,int ql,int qr)
        {
            if(l>qr||r<ql)return (ll)0;
            if(ql<=l&&r<=qr)return s2[x]%MOD;
            pushdown(x,l,r);
            int mid=(l+r)>>1;
            ll res=0;
            if(ql<=mid)res+=query(ls,l,mid,ql,qr);
            if(mid<qr)res+=query(rs,mid+1,r,ql,qr);
            return res%MOD;
        }
        void update(int x,int l,int r,int ql,int qr,ll v)
        {
            if(l>qr||r<ql)return;
            if(ql<=l&&r<=qr)
            {
                lz[x]=(lz[x]+v)%MOD;
                s2[x]=(s2[x]+mul(v,v,r-l+1)+mul(s1[x],2*v))%MOD;
                s1[x]=(s1[x]+mul(v,r-l+1))%MOD;
                return ;
            }
            pushdown(x,l,r);
            int mid=(l+r)>>1;
            update(ls,l,mid,ql,qr,v);
            update(rs,mid+1,r,ql,qr,v);
            pushup(x);
        }
        void debug(int x,int l,int r)
        {
            cout<<"x="<<x<<" l="<<l<<" r="<<r<<" s1[x]="<<s1[x]<<" s2[x]="<<s2[x]<<endl;
            if(l==r)return;
            int mid=(l+r)>>1;
            pushdown(x,l,r);
            debug(ls,l,mid);
            debug(rs,mid+1,r);
        }
        void debug(int l,int r)
        {
            debug(1,l,r);
            system("pause");
        }
        #undef ls
        #undef rs
    }sgt;
    vector<int> go[maxn];
    int n,m;
    int in[maxn],out[maxn],a[maxn],tot;
    void dfs(int u,int fa)
    {
        in[u]=++tot;
        sgt.val[tot]=a[u];
        for(auto v:go[u]){
            if(v==fa)continue;
            dfs(v,u);
        }
        out[u]=tot;
    }
    
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            go[a].push_back(b);
            go[b].push_back(a);
        }
    
        dfs(1,0);
    
        sgt.build(1,1,n);
        //debug();
    
        while(m--)
        {
            int op,x,y;
            cin>>op;
            if(op==1)
            {
                cin>>x>>y;
                sgt.update(1,1,n,in[x],out[x],y);
            }else
            {
                cin>>x;
                cout<<sgt.query(1,1,n,in[x],out[x])%MOD<<endl;
            }
    
        }
        return 0;
    }