题目链接
题目大意:
输入:
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; }