bzoj3730:震波

时间:2024-10-07 19:35:14

题意:给一棵树,只有点权无边权, ,每次询问求以一个点为中心,半径为k的全职和。

考虑动态树分治。我们对于每个点(点分树)维护两个树状数组。两个树状数组都以距离为下标,权值为内容。第一个树状数组维护子树中距离该点为k的权值和,第二个维护距离该点父亲距离为k的权值和。这样改权值时我们暴力爬树高,loglog复杂度(log的树高加上log的树状数组)。查询的时候一样爬树高,要注意容斥(把当前子树k的先加起来,往祖先上爬,如果距离小于k,假设为d,我们到祖先上去求一个k-d,再容斥掉原来这棵子树里被计算过的,这就是第二个树状数组的用处)。

时间复杂度0(nloglog),空间复杂度O(nlog)(如果用线段树还要加一个log。这里BB一句,为什么树状数组不会爆呢,因为你每一层开的大小为子树大小的话,每层总和n,总共log层,空间就是nlog的。其实就跟点分治的时间复杂度证明一样。用vector来开并且加上函数resize()就可以办到了。)

这道题花了整整一天才写出来。。。一直RE(实际是WA,毕竟防离线加密,如果答案错了后面输入都是错的),总结一下错误:

1.想的只用一个树状数组维护,实际上为了容斥必须要用上第二个树状数组。

2.更新时,一开始要把自己丢在自己的第二个树状数组里面

3.2这玩意肯定要写在爬树循环外面啊(你是SB吗)

4.应该用qsum而不是query去爬树高(一开始脑袋抽了。。)

5.往树上爬的时候是不会中途退出的,不会因为有一个祖先爬不上去就终止,说不定有一个爷爷就在你旁边你可以过去呢。

对于点分树的题就想象成爬山吧,我们用每一层的重心将点们分割开来,每次爬树高都是解锁区域,翻过一座高山。

还有,点分树自己脑补的板子实在太丑陋了。。这里膜拜一下ihopenot大佬,板子神快,我一开始好不容易调出来T了,参考了一下大佬的板子后就rank8了,真乃神人也!

 #include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 1e9
#define lowbit(i) ((i)&-(i))
int n,m,head[N],val[N],fa[N][],dis[N][],s[N],f[N],dep[N],rt,sz,cnt,ans;
bool vis[N];
vector<int>bit[N],fbit[N];
inline int read(){
int x=,f=; char a=getchar();
while(a>'' || a<'') {if(a=='-') f=-; a=getchar();}
while(a<='' && a>='') x=x*+a-'',a=getchar();
return x*f;
}
struct edges{
int to,next;
}e[*N];
inline void insert(){
int u=read(),v=read();
e[cnt]=(edges){v,head[u]};head[u]=cnt++;
e[cnt]=(edges){u,head[v]};head[v]=cnt++;
}
void getroot(int x,int father){
s[x]=; f[x]=;
for(int i=head[x];i>=;i=e[i].next){
if(vis[e[i].to] || father==e[i].to) continue;
getroot(e[i].to,x); s[x]+=s[e[i].to];
f[x]=max(f[x],s[e[i].to]);
}
f[x]=max(f[x],sz-s[x]);
if(f[x]<f[rt]) rt=x;
}
void getship(int x,int anc,int father,int d){
for(int i=head[x];i>=;i=e[i].next){
int v=e[i].to;
if(!vis[v] && v!=father) fa[v][++dep[v]]=anc,dis[v][dep[v]]=d,getship(v,anc,x,d+);
}
}
void Buildtree(int x){
vis[x]=; getship(x,x,,);
int all=sz; bit[x].resize(all+); fbit[x].resize(all+);
for(int i=head[x];i>=;i=e[i].next){
if(vis[e[i].to]) continue;
sz=s[e[i].to]; if(sz>s[x]) sz=all-s[x];
rt=; getroot(e[i].to,x); Buildtree(rt);
}
}
inline int qsum(int x,int k){
int ret=val[x],lim=bit[x].size()-; k=min(k,lim);
for(int i=k;i;i-=lowbit(i)) ret+=bit[x][i];
return ret;
}
inline int qsum2(int x,int k){
int ret=,lim=fbit[x].size()-; k=min(k,lim);
for(int i=k;i;i-=lowbit(i)) ret+=fbit[x][i];
return ret;
}
inline void change(int x,int v){
int d,lim;
d=dis[x][dep[x]]; lim=bit[x].size()-;
for(int j=d;j<=lim && j;j+=lowbit(j)) fbit[x][j]+=v;
for(int i=dep[x];i;i--){
d=dis[x][i]; lim=bit[fa[x][i]].size()-;
for(int j=d;j<=lim;j+=lowbit(j)) bit[fa[x][i]][j]+=v;
d=dis[x][i-];
for(int j=d;j<=lim && j;j+=lowbit(j)) fbit[fa[x][i]][j]+=v;
}
}
int query(int x,int k){
int ret=qsum(x,k);
for(int i=dep[x];i;i--) if(dis[x][i]<=k)
ret+=qsum(fa[x][i],k-dis[x][i])-qsum2(fa[x][i+],k-dis[x][i]);
return ret;
}
int main(){
n=read(); m=read(); memset(head,-,sizeof(head));
for(int i=;i<=n;i++) val[i]=read();
for(int i=;i<n;i++) insert();
f[]=INF; sz=n; getroot(,); Buildtree(rt);
for(int i=;i<=n;i++) fa[i][dep[i]+]=i;
for(int i=;i<=n;i++) change(i,val[i]);
while(m--){
int a=read(),b=read()^ans,c=read()^ans;
if(!a) ans=query(b,c),printf("%d\n",ans);
else change(b,c-val[b]),val[b]=c;
}
return ;
}