##### 題目描述 ：

在一片土地上有N個城市，通過N-1條無向邊互相連接，形成一棵樹的結構，相鄰兩個城市的距離為1，其中第i個城市的價值為value[i]。
不幸的是，這片土地常常發生地震，并且隨著時代的發展，城市的價值也往往會發生變動。
接下來你需要在線處理M次操作：
0 x k 表示發生了一次地震，震中城市為x，影響范圍為k，所有與x距離不超過k的城市都將受到影響，該次地震造成的經濟損失為所有受影響城市的價值和。
1 x y 表示第x個城市的價值變成了y。
為了體現程序的在線性，操作中的x、y、k都需要異或你程序上一次的輸出來解密，如果之前沒有輸出，則默認上一次的輸出為0

#### 題解：
第一道動態點分治題
感覺所有點分治的題的大體思路是這樣的：
先假定原樹的樹高是 $O(logn)$ 級別，并思考在原樹中怎么做。
想出來在原樹中的做法后再進行一遍點分治來進行優化。
而本題中，我們不僅僅需要點分治，而是動態點分治。
首先，考慮對每個點開一顆以距離為下標，價值為權值的線段樹，維護的是以該點為樹根，該點子樹中的節點相對與它的距離以及權值。

注：下文中提到的樹均為原樹，而非點分樹(一會我們再會說用動態點分治優化)

考慮修改操作(對 $x$ 進行修改)
直接修改似乎有些困難，可以轉換成對 $x$ 加上 $new(x)-old(x)$

?

?一步步跳父親，修改 [0? dis-k] 的的所有權值，然而這么做會有上圖中的問題：?

由祖先向修改點會延申 $dis-k$ 的距離，這一部分是完全多余的。

于是，我們對每個點再開一顆線段樹，以該點子樹中到父親距離為下標，維護權和。?

考慮統計答案：

邊向上跳邊加上 $dis-k$ 的貢獻，同時還要減掉那一部分多余的貢獻。

Code:

#include<bits/stdc++.h> #define setIO(s) freopen(s".in","r",stdin) #define maxn 3011111 #define N 200010 #define inf 0x7f7f7f using namespace std; int hd[N],nx[N],to[N],cnt; int n,m,val[N],vis[N]; void add(int u,int v) {nx[++cnt]=hd[u],hd[u]=cnt,to[cnt]=v; } namespace heavyedge{int dep[N],hson[N],fa[N],siz[N],top[N]; void dfs1(int u,int ff){dep[u]=dep[ff]+1,fa[u]=ff,siz[u]=1; for(int i=hd[u];i;i=nx[i]) if(to[i]!=ff) {dfs1(to[i],u),siz[u]+=siz[to[i]];if(siz[to[i]]>siz[hson[u]]) hson[u]=to[i]; }}void dfs2(int u,int tp){top[u]=tp; if(hson[u]) dfs2(hson[u],tp); for(int i=hd[u];i;i=nx[i]){if(to[i]==fa[u]||to[i]==hson[u]) continue; dfs2(to[i],to[i]); }}int LCA(int u,int v){while(top[u]!=top[v]) dep[top[u]] < dep[top[v]] ? v = fa[top[v]] : u = fa[top[u]]; return dep[u] < dep[v] ? u : v; }int main(){dfs1(1,0), dfs2(1,1); return 0; } }; int Dis(int u,int v) { return heavyedge::dep[u] + heavyedge::dep[v] - (heavyedge::dep[heavyedge::LCA(u,v)] << 1); } int siz[N],f[N],root,sn,Fa[N]; int GetRoot(int u,int ff) {siz[u] = 1,f[u] = 0; for(int i = hd[u]; i ; i = nx[i]) {if(to[i] == ff || vis[to[i]]) continue; GetRoot(to[i],u); siz[u] += siz[to[i]]; f[u] = max(f[u],siz[to[i]]); }f[u] = max(f[u],sn - siz[u]); if(f[u] < f[root]) root = u; } void dfs(int u) {vis[u] = 1; for(int i = hd[u]; i ; i = nx[i]){if(vis[to[i]]) continue; root = 0, sn = siz[to[i]], GetRoot(to[i],u); Fa[root] = u, dfs(root); } } struct Segment_Tree{int tot; struct Node{int l,r,v; }t[maxn<<1]; void update(int &o,int l,int r,int p,int w){if(!o) o = ++tot; t[o].v += w; if(l == r) return; int mid = (l + r) >> 1; if(p <= mid) update(t[o].l,l,mid,p,w); else update(t[o].r,mid + 1,r,p,w); }int query(int o,int l,int r,int L,int R){if(!o || l > r) return 0; if(l >= L && r <= R) return t[o].v; int ret = 0, mid = (l + r) >> 1; if(L <= mid) ret += query(t[o].l,l,mid,L,R); if(mid + 1 <= R) ret += query(t[o].r,mid + 1,r,L,R); return ret; } }T; int ans = 0,rt[N]; #define fax(x) (x + n) int Query(int x,int k) { int ret = T.query(rt[x],0,n,0,k); for(int i = x; Fa[i] ; i = Fa[i]) {int dis = Dis(x, Fa[i]); if(dis > k) continue; ret += T.query(rt[Fa[i]],0,n,0,k - dis); ret -= T.query(rt[fax(i)],0,n,0,k - dis); }return ret; } void Update(int x,int k) { T.update(rt[x],0,n,0,k); for(int i = x; Fa[i]; i = Fa[i]){int dis = Dis(x, Fa[i]); //正確性顯然T.update(rt[Fa[i]],0,n,dis,k);T.update(rt[fax(i)],0,n,dis,k); } } int main() {// setIO("input"); scanf("%d%d",&n,&m);for(int i = 1;i <= n; ++i) scanf("%d",&val[i]); for(int i = 1,u,v;i < n; ++i) scanf("%d%d",&u,&v), add(u,v),add(v,u); heavyedge :: main(); f[0] = inf, sn = n,root = 0,GetRoot(1,0), dfs(root); for(int i = 1;i <= n; ++i) Update(i,val[i]); while(m--){int x,y,opt; scanf("%d%d%d",&opt,&x,&y); x ^= ans, y ^= ans; if(opt == 0) printf("%d\n",ans = Query(x,y)); if(opt == 1) Update(x,y-val[x]),val[x]=y; }return 0; }

總結

以上是生活随笔為你收集整理的bzoj 3730: 震波 动态点分治+树链剖分+线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

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