Description

"奋战三星期，造台计算机"。小G响应号召，花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些

。普通计算机能计算数列区间和，而普通计算姬能计算树中子树和。更具体地，小G的计算姬可以解决这么个问题

：给定一棵n个节点的带权树，节点编号为1到n，以root为根，设sum[p]表示以点p为根的这棵子树中所有节点的权

值和。计算姬支持下列两种操作:

1 给定两个整数u,v，修改点u的权值为v。

2 给定两个整数l,r，计算sum[l]+sum[l+1]+....+sum[r-1]+sum[r]

尽管计算姬可以很快完成这个问题，可是小G并不知道它的答案是否正确，你能帮助他吗？

Solution

分块。块内直接统计，单点的sum树状数组暴力加起来

为了方便修改，g[a][i]表示点a对块[i]的贡献

另外，好坑啊这题会爆long long

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 100007using namespace std;typedef unsigned long long LL;int n,m,init,num,head[MAXN],g[MAXN][330],cnt=0;LL c[MAXN],d[MAXN],sum[MAXN],blocks[330];int dfn_clock=0,in[MAXN],out[MAXN],a[MAXN];LL read(){    LL x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;}struct Node{    int next,to;}Edges[MAXN*2];void addedge(int u,int v){    Edges[++cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v;}int lowbit(int x){
   return x&-x;}void add(int pos,int x){    while(pos<=n)    {        c[pos]+=x;        pos+=lowbit(pos);    }}LL query(int pos){    LL res=0;    while(pos>0)    {        res+=c[pos];        pos-=lowbit(pos);    }    return res;}void dfs(int u,int f){    dfn_clock++;in[u]=dfn_clock;    sum[u]=d[u];    a[(u-1)/init]++;    for(int i=0;i
          
           =((b-1)/init)*init+1;i--) res+=query(out[i])-query(in[i]-1); } printf("%llu\n",res);}int main(){ memset(head,-1,sizeof(head)); n=read(),m=read(); init=(int)sqrt(n+0.1); num=(n-1)/init+1; for(int i=1;i<=n;i++) d[i]=read(); int root; for(int i=1;i<=n;i++) { int u=read(),v=read(); if(!u){root=v;continue;} addedge(u,v); addedge(v,u); } dfs(root,0); for(int i=1;i<=n;i++) add(in[i],d[i]); for(int i=1;i<=m;i++) { int opt=read(),a=read();LL b=read(); if(opt==1)Change(a,b); else Query(a,b); } return 0;}