[文章目录]
Description
给定一棵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]
n<=10^5 m<=10^5
对节点编号分块，递推统计每个节点修改权值对于所有块内编号点的sum的影响。对于零散部分，线段树维护dfs序即可。
复杂度O(n√(nlogn))
话说我肿么写过的题都不会了。。。
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
typedef long long ll;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
return x;
}
int n,m,lim,bl,root,b[N],r[N],d[N];
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y) {to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;}
int in[N],out[N],tim,M,siz[N][350];
ll s[N<<2],sum[N],ans[350];
void dfs(int x,int pre)
{
for(int i=0;i<=lim;++i) siz[x][i]=siz[pre][i];
siz[x][b[x]]++; in[x]=++tim; sum[x]=s[M+tim]=d[x];
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dfs(to[i],x),sum[x]+=sum[to[i]];
out[x]=tim;
}
void fix(int x,int y) {s[x=x+M]=y; while(x>>=1) s[x]=s[x<<1]+s[x<<1|1];}
ll query(int l,int r)
{
ll re=0;
for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1) re+=s[l^1];
if(r&1) re+=s[r^1];
}
return re;
}
int main()
{
n=read(); m=read();
bl=(int)sqrt(n)+1; lim=n/bl;
int i,x,y;
for(i=1;i<=n;++i) b[i]=i/bl,r[i]= b[i-1]==b[i] ? r[i-1]+1 : 0;
for(i=1;i<=n;++i) d[i]=read();
for(M=1;M<=n+1;M<<=1);
for(i=1;i<=n;++i)
{
x=read(); y=read();
if(x) add(x,y),add(y,x);
else root=y;
}
dfs(root,0);
for(i=M-1;i;--i) s[i]=s[i<<1]+s[i<<1|1];
for(i=1;i<=n;++i) ans[b[i]]+=sum[i];
unsigned long long fna; int L,R;
while(m--)
{
if(read()==1)
{
x=read(); y=read();
fix(in[x],y);
y-=d[x];
for(i=0;i<=lim;++i) ans[i]+=(ll)y*siz[x][i];
d[x]+=y;
}
else
{
x=read(); y=read(); fna=0;
L= r[x]==0 ? b[x] : b[x]+1;
R= r[y]==bl-1 ? b[y] : b[y]-1;
if(L>R) for(i=x;i<=y;++i) fna+=query(in[i],out[i]);
else
{
for(i=L;i<=R;++i) fna+=ans[i];
for(i=L*bl-1;i>=x;--i) fna+=query(in[i],out[i]);
for(i=R*bl+bl;i<=y;++i) fna+=query(in[i],out[i]);
}
printf("%llu\n",fna);
}
}
return 0;
}