初見安～這里是傳送門：洛谷P6329 【模板】點分樹 | 震波

一、點分樹

其實你會點分治的話，點分樹就是把點分治時的重心提出來重新連城一棵樹。

比如當前點是u，求出子樹v的重心root后將root與u連邊。如此遞歸下去，就是一棵點分樹。

有什么用呢？因為重構了樹的結構，并且保證了深度不超過logn，所以可以把一些極其暴力的操作的復雜度變正確。

比如震波這個題。

二、題解

題意很顯然：單點修改和求距某點距離在K以內的所有點的點權和。

借用點分樹的性質，我們建樹過后考慮如何維護這個暴力（不容易想到 算是點分樹自帶的套路？）。另表示點u在點分樹上的子樹內距離在i以內的點的點權和。注意，這里可能對產生貢獻的點是u在點分樹上的子樹內的點，但是距離是原樹的距離。我們先不考慮修改，如果是詢問的話，顯然可以用統計一部分的點。但是因為是重構過的，所以有可能有些點還在上面，所以我們要挨著往上走，也就是從u暴力跳到整個點分樹的樹根去。并且點分樹上點在原樹上不一定相鄰，所以對于當前某個父親x，所求為距離點u距離為K以內的點的點權和，x的貢獻為。

到這里就會有個問題：是否存在這樣一個被統計到的點v，fa[u]是點分樹上u的父親，路徑u->fa[u]->v有重復經過某條邊，但依舊在K以內導致v被計算了兩次？那必然存在。考慮如何容斥掉這種情況。其實這種重復的情況出現只有當原樹上u、v、fa[u]是這樣的祖先關系時才會出現（大概？）也就是，v是u的祖先，fa[u]又是v的祖先。這樣的話如果會重復遍歷，那么點分樹上v一定在u的子樹內。換言之，我們會重復遍歷到v完全是因為在u的時候計算過了一次，在又計算了一次。所以減去u子樹內對fa[u]的貢獻即可。換言之我們再搞一個表示點分樹上u的子樹內的點到fa[u]距離為i的點的點權和。容斥掉即可。

修改也很容易，因為每個點的點權會影響到的就只有它的所有祖先，是log級別的。暴力跳上去就好。

但是這個題因為求的是前K個，所以需要一個前綴和。這個就用樹狀數組了，總的時間復雜度多一個log，為nlog^2n。

以及，因為n個點，每個點都有一個樹狀數組，空間不可能開n^2，所以考慮實際距離應該在size[u]以內，卡著子樹大小size[u]開就好。空間復雜度也是nlogn的。（可是我卡著開就全RE了不知道為什么……）

上代碼：

#include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<cstdio> #include<cmath> #include<queue> #define maxn 100005 using namespace std; typedef long long ll; int read() {int x = 0, f = 1, ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();return x * f; }struct edge {int to, nxt;} e[maxn << 1]; int head[maxn], k = 0; void add(int u, int v) {e[k] = {v, head[u]}; head[u] = k++;}int n, m, a[maxn]; int dep[maxn], st[maxn << 1][20], num[maxn], tot = 0; int get_min(int a, int b) {return dep[a] < dep[b]? a : b;} void dfs(int u, int fa) {st[++tot][0] = u; num[u] = tot;for(int i = head[u], v; ~i; i = e[i].nxt) {v = e[i].to; if(v == fa) continue;dep[v] = dep[u] + 1; dfs(v, u); st[++tot][0] = u;} }int root, size[maxn], part[maxn], max_part, all_part = 0; bool vis[maxn]; void get_root(int u, int fa) {size[u] = 1; part[u] = 0; all_part++;for(int i = head[u], v; ~i; i = e[i].nxt) {v = e[i].to; if(v == fa || vis[v]) continue;get_root(v, u); size[u] += size[v];part[u] = max(part[u], size[v]);}part[u] = max(part[u], max_part - size[u]);if(part[u] < part[root]) root = u; }int sz[maxn], fa[maxn]; vector<int> t[maxn][2]; void slv(int u) {vis[u] = true; sz[u] = all_part + 1;//allpart是求重心的時候算的整個子樹大小，但是要+1才行，按理說不該有這么遠的點……？QwQt[u][0].resize(sz[u] + 1); t[u][1].resize(sz[u] + 1);//這里+1是因為算上0位置for(int i = head[u], v; ~i; i = e[i].nxt) {v = e[i].to; if(vis[v]) continue;max_part = size[v]; all_part = root = 0; get_root(v, u);fa[root] = u; slv(root);} }int get_dis(int u, int v) {register int x = num[u], y = num[v]; if(x > y) swap(x, y);register int len = (int)log2(y - x + 1), lca = get_min(st[x][len], st[y - (1 << len) + 1][len]);return dep[u] + dep[v] - (dep[lca] << 1); } //兩行樹狀數組 void ist(int u, int op, int x, int w) {x++; for(; x <= sz[u]; x += (x & -x)) t[u][op][x] += w;} int ask(int u, int op, int x) {x++; int res = 0; for(x = min(x, sz[u]); x; x -= (x & -x)) res += t[u][op][x]; return res;} void update(int u, int val) {//樓上樹狀數組，求答案的時候一定記得上界取minfor(int i = u; i; i = fa[i]) ist(i, 0, get_dis(u, i), val);for(int i = u; fa[i]; i = fa[i]) ist(i, 1, get_dis(u, fa[i]), val); }signed main() {n = read(), m = read(); memset(head, -1, sizeof head);for(int i = 1; i <= n; i++) a[i] = read();for(int i = 1, u, v; i < n; i++) u = read(), v = read(), add(u, v), add(v, u);dfs(1, 0);root = 0, max_part = part[0] = n; get_root(1, 0);slv(root);//建點分樹dep[0] = n + n;for(int i = 1; (1 << i) <= tot; i++) for(int j = 1; j + (1 << i) <= tot; j++) st[j][i] = get_min(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);//O1求LCA，st表for(int i = 1; i <= n; i++) update(i, a[i]);//更新值int ans = 0;while(m--) {register int op = read(), x = read(), y = read();x ^= ans, y ^= ans;if(!op) {ans = ask(x, 0, y);for(int i = x; fa[i]; i = fa[i]) {register int d = get_dis(x, fa[i]);//往上跳。因為點分樹距離不單調所以都要求if(y >= d) ans += ask(fa[i], 0, y - d) - ask(i, 1, y - d);}printf("%d\n", ans);} else update(x, y - a[x]), a[x] = y;}return 0; }

迎評：）
——End——

?

?

總結

以上是生活随笔為你收集整理的洛谷·【模板】点分树 | 震波【including 点分树的全部內容，希望文章能夠幫你解決所遇到的問題。

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