題目傳送門

題目大意： 有一棵 $n$ 個帶權點的樹，所有邊的長度都是 $1$，現在有兩種操作。操作 $1$：詢問 $x$ 周圍與它距離不超過 $k$ 的點的權值和（包括自己）；操作 $24：修改某點的權值。

題解

考慮使用動態點分治。

對于每一次詢問，可以從 $x$ 開始沿著點分樹向上走，對于每個到達的點（也就是重心），我們可以統計答案，該點能提供的貢獻就是深度小于等于 $k?deep[x]$（這里的 $x$ 的深度（即 $deep[x]$）是相對于該重心而言的）的點的貢獻和，但是還要減去與 $x$ 同一棵子樹內的貢獻。

對于每一次修改，我們依然沿著點分樹走，沿途修改對于每個重心而言深度為 $deep[x]$ 的點的貢獻和。

發現對于每個重心，我們有兩種操作，一是統計小于等于某深度的點的權值和，一種是修改某深度的點的權值和，發現正是個改點求段操作，于是可以用樹狀數組愉快的解決~

還有一個坑點，就是在點分樹上求解的時候，不能在發現某個時候 $k?deep[x]<0$ 就停下，不繼續向上跳求解。因為在點分樹上跳時，是不能保證重心到 $x$ 的距離遞增的。

具體細節看代碼吧：

#include <cstdio> #include <cstring> #include <map> #include <vector> #include <algorithm> using namespace std; #define maxn 100010int n,m; int value[maxn]; struct node{int y,next;}; node e[maxn*2]; int first[maxn]; void buildroad(int x,int y)//建邊 {static int len=0;e[++len]=(node){y,first[x]};first[x]=len; } struct trarr{//樹狀數組vector<int> tr;int l;trarr(){tr.clear();tr.push_back(0);l=0;}//這個push_back是用來填充數組的0位置的inline int lowbit(int x){return x&(-x);}void add(int x,int y){for(;x<=l;x+=lowbit(x))tr[x]+=y;}int sum(int x){int ans=0;for(;x>=1;x-=lowbit(x))ans+=tr[x];return ans;} }; bool v[maxn]; int Size,size[maxn],mson[maxn],root; void getroot(int x,int fa)//找重心 {size[x]=1;mson[x]=0;for(int i=first[x];i;i=e[i].next){int y=e[i].y;if(v[y]||y==fa)continue;getroot(y,x);size[x]+=size[y];if(size[y]>mson[x])mson[x]=size[y];}if(Size-size[x]>mson[x])mson[x]=Size-size[x];if(mson[x]<mson[root])root=x; } vector<int>a[maxn];//a[i][j] : 以i為重心的子樹中，深度為j的點的權值的總和 int aa[maxn];//aa[i] : 以i為重心的子樹的最大深度 trarr atree[maxn];//用來維護a數組的樹狀數組 struct wulala{int arr[maxn];}; vector<wulala> dis;//dis[i].arr[j] ： 點分治第i層中，點j到重心的距離 //因為在點分治的每一層中，每個點只屬于一個重心，所以可以這樣表示該層中x到重心的距離 wulala newwulala; int deepp=0;//點分治層數 void getdis_a(int x,int fa,int tr,int deep,int dep)//統計每個點到重心的距離以及以該重心為根的子樹內每個深度內的點權和 {if(deep>aa[tr])aa[tr]++,a[tr].push_back(0);a[tr][deep]+=value[x];dis[dep].arr[x]=deep;for(int i=first[x];i;i=e[i].next){int y=e[i].y;if(y==fa||v[y])continue;getdis_a(y,x,tr,deep+1,dep);} } int son[maxn]; map<int,int> s[maxn];//給每個兒子重新編號，s[x][y]表示y是x的第幾個兒子 vector< vector<int> >b[maxn];//b[i][j][k] : 以i為重心的子樹中，i的第j棵子樹中深度為k的點權和，此時的深度 vector<int> bb[maxn];//以x為重心的子樹中，x的第y棵子樹的深度 vector<trarr> btree[maxn];//維護b的樹狀數組 vector<int> newvec; void getdis_b(int x,int fa,int tr,int num,int deep) {if(deep>bb[tr][num])bb[tr][num]++,b[tr][num].push_back(0);b[tr][num][deep]+=value[x];for(int i=first[x];i;i=e[i].next){int y=e[i].y;if(y==fa||v[y])continue;getdis_b(y,x,tr,num,deep+1);} } int fa[maxn],con[maxn]; int deep_focus[maxn];//每個重心在點分樹中的深度 void buildtree(int x,int deep,int ssize) {if(deep>deepp)deepp++,dis.push_back(newwulala);v[x]=true;deep_focus[x]=deep;getdis_a(x,0,x,0,deep);for(int i=first[x];i;i=e[i].next){int y=e[i].y;if(v[y])continue;son[x]++;//x的兒子數量s[x][y]=son[x];b[x].push_back(newvec);bb[x].push_back(-1);//注意，是-1不是0，結合上面代碼就能理解了getdis_b(y,x,x,son[x],0);root=0;Size=size[y]<size[x]?size[y]:(ssize-size[x]);getroot(y,0);fa[root]=x;con[root]=y;//fa表示root的父親（在點分樹中），con表示root在fa[root]的哪一個兒子的子樹中（這個兒子是指原樹中的）buildtree(root,deep+1,(size[y]<size[x]?size[y]:(ssize-size[x])));} } void buildatree()//將a數組用樹狀數組atree維護起來 {for(int i=1;i<=n;i++){for(int j=1;j<=aa[i];j++)atree[i].tr.push_back(0);atree[i].l=aa[i];for(int j=1;j<=aa[i];j++)atree[i].add(j,a[i][j]);} } trarr newtr; void buildbtree()//將b數組用樹狀數組btree維護起來 {for(int i=1;i<=n;i++){btree[i].push_back(newtr);for(int j=1;j<=son[i];j++){btree[i].push_back(newtr);for(int k=1;k<=bb[i][j];k++)btree[i][j].tr.push_back(0);btree[i][j].l=bb[i][j];for(int k=1;k<=bb[i][j];k++)btree[i][j].add(k,b[i][j][k]);}} } int last=0; void work(int x,int dist){ last+=atree[x].sum(min(dist,aa[x]))+a[x][0]; } //work統計在以x為重心的子樹中，與x的距離小于等于dist的點權和 void go(int x,int y,int dist,int point)//統計以在以x為重心的子樹中，與point的距離小于等于dist的點權和 //y表示 point在x的y這個兒子的子樹中 {int need=dist-dis[deep_focus[x]].arr[point];//need表示將要求以x為重心的子樹中深度小于等于need的點權和if(need>=0)//如果小于0則不能產生貢獻{last+=atree[x].sum(min(aa[x],need))+a[x][0];//求出點權和last-=btree[x][s[x][y]].sum(min(need-1,bb[x][s[x][y]]))+(need>0?b[x][s[x][y]][0]:0);//減去以y為根的子樹產生的貢獻//因為0這個位置是不能用樹狀數組維護的，于是我們單獨考慮，change函數中同理}if(fa[x])go(fa[x],con[x],dist,point); } void change(int x,int y,int newval,int point)//newval表示point這個節點的新權值 {atree[x].add(dis[deep_focus[x]].arr[point],-value[point]);//減去原來的權值atree[x].add(dis[deep_focus[x]].arr[point],newval);//加上現在的權值if(dis[deep_focus[x]].arr[point]==1)b[x][s[x][y]][0]=newval;//單獨考慮0位置else btree[x][s[x][y]].add(dis[deep_focus[x]].arr[point]-1,-value[point]),btree[x][s[x][y]].add(dis[deep_focus[x]].arr[point]-1,newval);if(fa[x])change(fa[x],con[x],newval,point); } //-------------------------------------------------------------- //以下為輸入輸出優化（不卡卡常過不了= =） inline char cn() {static char buf[1000010],*t1=buf,*t2=buf;return t1==t2&&(t2=(t1=buf)+fread(buf,1,1000000,stdin),t1==t2)?EOF:*t1++; } void read(int &x) {x=0;char ch=cn();while(ch<'0'||ch>'9')ch=cn();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=cn(); } char buff[1000020]; int len=-1; int output[20],lo; void add(int x) {lo=0;while(x>0)output[++lo]=x%10,x/=10;while(lo>0)buff[++len]=output[lo--]+'0';buff[++len]='\n';if(len>1000000)fwrite(buff,1,len,stdout),len=-1; } //--------------------------------------------------------------int main()//主函數就沒什么好講的了，其中包含的函數的意義已經講明白了（其實只是因為懶。。） { // freopen("data.txt","r",stdin); // freopen("mine.txt","w",stdout);read(n);read(m);for(int i=1;i<=n;i++)read(value[i]);for(int i=1;i<n;i++){int x,y;read(x);read(y);buildroad(x,y);buildroad(y,x);}root=0;Size=n;mson[0]=999999999;memset(aa,-1,sizeof(aa));for(int i=1;i<=n;i++)b[i].push_back(newvec),bb[i].push_back(0);getroot(1,0);dis.push_back(newwulala);buildtree(root,1,n);buildatree();buildbtree();for(int i=1;i<=m;i++){int id,x,y;read(id);read(x);read(y);x^=last,y^=last;if(id==0){last=0;work(x,y);if(fa[x])go(fa[x],con[x],y,x);add(last);}else{a[x][0]=y;if(fa[x])change(fa[x],con[x],y,x);value[x]=y;}}fwrite(buff,1,len,stdout); }

總結

以上是生活随笔為你收集整理的BZOJ 3070 震波 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。