正題

題目鏈接:https://www.luogu.com.cn/problem/P6329

---

解題思路

給出$n$個點的一棵樹，每個點有權(quán)值，有$m$次操作

修改一個點$x$的權(quán)值為$y$

詢問距離點$x$不超過$k$的所有點點權(quán)和

---

解題思路

點分樹的模板題，先點分治構(gòu)造出點分樹，然后在上面維護信息。

對于每個點維護一個點分子樹內(nèi)，與該點的距離為下標(biāo)，點權(quán)為權(quán)值的的樹狀數(shù)組，然后查詢的時候直接查距離不超過$k?dis(now,x)$的就好了。

發(fā)現(xiàn)與點分父節(jié)點會有算重的情況，這個時候順便維護一個以與父節(jié)點的距離為下標(biāo)的樹狀數(shù)組，然后減去重復(fù)的答案就好了。

時間復(fù)雜度$O(n{\log }^{2}n)$。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define lowbit(x) (x&-x) using namespace std; const int N=1e5+10,T=18,inf=1e9; struct node{int to,next; }a[N<<1]; int n,m,tot,cnt,num,root,fr,val[N]; int ls[N],f[N<<1][T],rfn[N],dep[N]; int fa[N],siz[N],lg[N<<1],mx; bool v[N]; struct BIT{vector<int> t;int n;void Init(int x){x++;t.resize(x);n=x;return;}void Change(int x,int val){x++;while(x<=n){t[x-1]+=val;x+=lowbit(x);}return;}int Ask(int x){if(x<0)return 0;int ans=0;x++;if(x>n)x=n;while(x){ans+=t[x-1];x-=lowbit(x);}return ans;} }s1[N],s2[N]; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x,int fa){dep[x]=dep[fa]+1;f[++cnt][0]=x;rfn[x]=cnt;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dfs(y,x);f[++cnt][0]=x;}return; } void groot(int x,int fa){siz[x]=1;int f=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y]||y==fa)continue;groot(y,x);siz[x]+=siz[y];f=max(f,siz[y]);}f=max(f,num-siz[x]);if(f<fr)root=x,fr=f;return; } void calc(int x,int fa,int dep){mx=max(mx,dep);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa||v[y])continue;calc(y,x,dep+1);}return; } void Build(int x,int h){v[x]=1;int S=num,z=fr;mx=0;calc(x,x,0);s1[x].Init(mx);s2[x].Init(h);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y])continue;num=(siz[y]>siz[x])?(S-siz[x]):siz[y];mx=0;calc(y,x,1);fr=inf;groot(y,x);y=root;fa[y]=x;Build(y,mx);}return; } void Init(){dfs(1,1);for(int i=2;i<=cnt;i++)lg[i]=lg[i>>1]+1;for(int j=1;(1<<j)<=cnt;j++)for(int i=1;i+(1<<j)-1<=cnt;i++){int x=f[i][j-1],y=f[i+(1<<j-1)][j-1];f[i][j]=(dep[x]<dep[y])?x:y;}fr=inf;num=n;groot(1,1);Build(root,0);return; } int LCA(int l,int r){l=rfn[l];r=rfn[r];if(l>r)swap(l,r);int z=lg[r-l+1];int x=f[l][z],y=f[r-(1<<z)+1][z];return (dep[x]<dep[y])?x:y; } int dis(int x,int y) {return dep[x]+dep[y]-2*dep[LCA(x,y)];} void Updata(int x,int val){int now=x;while(now){s1[now].Change(dis(now,x),val);if(fa[now])s2[now].Change(dis(fa[now],x),val);now=fa[now];}return; } int Ask(int x,int k){int ans=0,now=x;ans=s1[x].Ask(k);while(fa[now]){int d=dis(fa[now],x);ans+=s1[fa[now]].Ask(k-d);if(fa[now])ans-=s2[now].Ask(k-d);now=fa[now];}return ans; } int main() {// freopen("P6329_1.in","r",stdin);// freopen("data.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&val[i]);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}Init();for(int i=1;i<=n;i++)Updata(i,val[i]);int last=0;while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);x^=last;y^=last;if(op){Updata(x,y-val[x]);val[x]=y;}elseprintf("%d\n",last=Ask(x,y));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P6329-[模板]点分树 | 震波的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。