牛客小白月赛9 D、书上求和（DFS序+线段树）

题目链接
题目大意：


输入：
5 5
0 0 0 0 0
1 2
1 3
3 4
3 5
1 1 3
1 3 7
1 4 5
1 5 6
2 1
输出：
599

总体思路：
因为是对一棵子树整体进行操作+k,所以我们可以用DFS序列将一棵树转化为一个序列，然后再在序列中用线段树来进行区间操作。线段树维护平方和也是老套路了。

代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=23333;
ll n,q;
ll a[100005];//记录每个点的初始值
//int b[100005];
ll dfsxu[100005];//DFS序
ll s[100005],e[100005];//s进点序，e出点序，一个子树根节点的进点序和出点序的序列解释这棵子树的DFS序
ll h[100005],t[100005*2],ne[100005*2];
ll inx;
ll op,x,y;
ll l,r;
struct ty{
    ll l,r;
    ll psum;//记录平方和 
    ll sum;//记录一次方和 
    ll lazy;//记录增加的K 
}; 
ty tr[100005*4]; 

void add(ll x,ll y){
    t[inx]=y;ne[inx]=h[x];h[x]=inx++; 
    return ;
}

ll id,len;
void dfs(ll u,ll fa){
    s[u]=++id;
    dfsxu[++len]=u;
    for(ll i=h[u];i!=-1;i=ne[i]){
        ll to=t[i];
        if(to==fa) continue;
        dfs(to,u);
    }
    e[u]=id;
    return ;
}

void pushup(ll u){
    tr[u].psum=(tr[u<<1].psum+tr[u<<1|1].psum)%mod;
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%mod;
    tr[u].lazy=0;
    return ;
}

void build(ll u,ll l,ll r){
    tr[u].l=l;tr[u].r=r;
    tr[u].lazy=0;
    if(l==r){
        tr[u].psum=a[dfsxu[l]]*a[dfsxu[l]]%mod;
        tr[u].sum=a[dfsxu[l]];
        tr[u].lazy=0;
        return ;
    }
    ll mind=(l+r)>>1;
    build(u<<1,l,mind);
    build(u<<1|1,mind+1,r);
    pushup(u);
    return ;
} 

void pushdown(ll u){
    if(!tr[u].lazy) return ;
    tr[u<<1].psum=(tr[u<<1].psum%mod+2*tr[u].lazy*tr[u<<1].sum%mod+(tr[u<<1].r-tr[u<<1].l+1)*tr[u].lazy*tr[u].lazy%mod)%mod;
    tr[u<<1|1].psum=(tr[u<<1|1].psum%mod+2*tr[u].lazy*tr[u<<1|1].sum%mod+(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].lazy*tr[u].lazy%mod)%mod;
    tr[u<<1].sum=(tr[u<<1].sum+(tr[u<<1].r-tr[u<<1].l+1)*tr[u].lazy%mod)%mod;
    tr[u<<1|1].sum=(tr[u<<1|1].sum+(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].lazy%mod)%mod;
    tr[u<<1].lazy=(tr[u<<1].lazy+tr[u].lazy)%mod;
    tr[u<<1|1].lazy=(tr[u<<1|1].lazy+tr[u].lazy)%mod;
    tr[u].lazy=0;
    return ;
}

void modify(ll u,ll l,ll r,ll k){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].psum=(tr[u].psum%mod+2*k*tr[u].sum%mod+(tr[u].r-tr[u].l+1)*k*k%mod)%mod;
        tr[u].sum=(tr[u].sum+(tr[u].r-tr[u].l+1)*k%mod)%mod;
        tr[u].lazy=(tr[u].lazy+k)%mod;
        return ;
    }
    pushdown(u);
    ll mind=(tr[u].l+tr[u].r)>>1;
    if(l<=mind) modify(u<<1,l,r,k);
    if(r>mind) modify(u<<1|1,l,r,k);
    pushup(u);
    return ;
}

ll query(ll u,ll l,ll r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].psum%mod;
    } 
    pushdown(u);
    ll mind=(tr[u].l+tr[u].r)>>1;
    ll ans=0;
    if(l<=mind) ans=(ans+query(u<<1,l,r))%mod;
    if(r>mind) ans=(ans+query(u<<1|1,l,r))%mod;
    pushup(u);
    return ans;
}

int main(){
    for(ll i=0;i<=100001;i++) h[i]=-1;
    scanf(" %lld %lld",&n,&q);
    for(ll i=1;i<=n;i++) scanf(" %lld",&a[i]);
    for(ll i=1;i<n;i++){
        scanf(" %lld %lld",&x,&y);
        add(x,y); add(y,x);
    }
    dfs(1,-1);//求DFS序
    build(1,1,n);//建线段树 
    for(ll i=1;i<=q;i++){
        scanf(" %lld",&op);
        if(op==1){
            scanf(" %lld %lld",&x,&y);
            modify(1,s[x],e[x],y);
        }
        else{
            scanf(" %lld",&x);
            printf("%lld\n",query(1,s[x],e[x])%mod);
        }
    }
    return 0;
}