一道奇奇怪怪的数据结构题？
把树线性化，然后分块维护吧。
为了加速，求和用树状数组维护每个块的值。
#include<bits/stdc++.h> #define N 100010 #define M 320 using namespace std; typedef long long ll; typedef unsigned long long ull; struct Edge{int u,v,next;}G[N*2]; ll c[N],ans[N],val[N]; int cnt,tot,head[N],block,rt,tpos[N],pos[N],size[N],num,n,m; int lx[M],rx[M],f[M][N]; void addedge(int u,int v){ G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot; G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot; } inline int lowbit(int x){return (x&(-x));} inline void add(int x,ll v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;} inline ll ask(int x){ ll ans=0; for(int i=x;i;i-=lowbit(i))ans+=c[i]; return ans; } void dfs(int u,int fa){ for(int i=1;i<=num;i++)f[i][u]=f[i][fa];f[pos[u]][u]++; tpos[u]=++cnt;size[u]=1; add(tpos[u],val[u]); for(int i=head[u];i;i=G[i].next){ int v=G[i].v;if(v==fa)continue; dfs(v,u); size[u]+=size[v]; } } void change(int x,ll v){ add(tpos[x],v-val[x]); for(int i=1;i<=num;i++)ans[i]+=(ll)f[i][x]*(v-val[x]); val[x]=v; } ull query(int l,int r){ ull ret=0; for(int i=pos[l]+1;i<=pos[r]-1;i++)ret+=ans[i]; if(pos[l]==pos[r]){ for(int i=l;i<=r;i++)ret+=ask(tpos[i]+size[i]-1)-ask(tpos[i]-1); return ret; } if(l==lx[pos[l]])ret+=ans[pos[l]]; else for(int i=l;i<=rx[pos[l]];i++)ret+=ask(tpos[i]+size[i]-1)-ask(tpos[i]-1); if(r==rx[pos[r]])ret+=ans[pos[r]]; else for(int i=lx[pos[r]];i<=r;i++)ret+=ask(tpos[i]+size[i]-1)-ask(tpos[i]-1); return ret; } inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } inline ll readll(){ ll f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int main(){ n=read();m=read(); for(int i=1;i<=n;i++)val[i]=readll(); for(int i=1;i<=n;i++){ int u=read(),v=read(); if(!u)rt=v; else addedge(u,v); } block=(int)sqrt(n);num=n%block==0?n/block:n/block+1; for(int i=1;i<=n;i++)pos[i]=(i-1)/block+1; dfs(rt,0); for(int i=1;i<=num;i++){ lx[i]=(i-1)*block+1;rx[i]=min(i*block,n); for(int j=lx[i];j<=rx[i];j++)ans[i]+=ask(tpos[j]+size[j]-1)-ask(tpos[j]-1); } while(m--){ int opt=read(),x=read(),y=read(); if(opt==1)change(x,(ll)y); else printf("%llu ",query(x,y)); } return 0; }