点分树
_MengShang_ · · 个人记录
点分树
- 前置知识:
点分治,树状数组,线段树等。 - 大致思路:
把点分治的过程离线下来,
将当前分治到的树重心与上一层的树重心连边,得到重构后的点分树。
然后考虑问题在原树上所求,转到点分树后的特点,以及如何维护。 - 例题:
- P6329【模板】点分树 | 震波
- 题意:
有
n 个城市,通过n-1 条无向边互相连接,形成一棵树的结构,
相邻两个城市的距离为1 ,其中第i 个城市的价值为a_i 。
你需要在线处理m 次操作:0 x k表示发生了一次地震,震中城市为x ,影响范围为k ,所有与x 距离不超过k 的城市都将受到影响,该次地震造成的经济损失为所有受影响城市的价值和。1 x y表示第x 个城市的价值变成了y 。
为了体现程序的在线性,操作中的
x 、y 、k 都需要异或上一次的输出来解密,
如果之前没有输出,则默认上一次的输出为0 。- 做法:
建立点分树,观察到,若地震中心为
x ,则离x 距离小于K 的点为以下两种之一:- 在点分树中
x 的子树内 - 在点分树中
x 的子树外
显然第一种很好维护信息,
我们只需要在每个点开一棵树状数组BIT ,BIT.ask(k) 为到点x 距离小于等于k 的点权值和。接下来再思考第二种。 我们考虑容斥,
注意到对于在点分树中x 的子树外的,
若我们从x 点向上跳,
则BIT[fa[x]].ask(k-dis(fa[x],x)) 与原x 点子树内的重合部分,
可以再开一个BIT2[x].ask(k) ,
记录x 点的父节点到x 子树内点距离为k 的点的权值。至此,本题思路大致结束,只需在思考修改和查询的具体实现即可。
详见代码。
- 代码:
#include <bits/stdc++.h> using namespace std; #define LL long long #define F(i, x, y) for (int i = x; i <= y; ++i) #define U(i, y, x) for (int i = y; i >= x; --i) #define pbk push_back namespace IO{ template <typename T> inline void read(T &x) { x = 0; char ch = getchar(); bool w = 1; while (!isdigit(ch)) { if (ch == 0x2d) w = 0; ch = getchar(); } while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 0x30); ch = getchar(); } x = w ? x : -x; } template <typename T> inline void write(T x) { if (x < 0) putchar(0xa), x = -x; if (x > 9) write(x / 0xa); putchar(x % 0xa + 0x30); } } using namespace IO; #define N 100005 int n, m, a[N], ans; vector<int> e[N]; class BIT{ private : vector<int> bit; inline int lowbit(int x) { return x & -x; } public : inline void build(int x) { F(i, 0, x + 1) bit.pbk(0); } inline void add(int x, int v) { for (int i = x; i < (int) bit.size(); i+= lowbit(i)) { bit[i]+= v; } } inline int ask(int x) { int res = 0; x = min(max(0, x), (int) bit.size() - 1); for (int i = x; i > 0; i-= lowbit(i)) { res+= bit[i]; } return res; } } dis1[N], dis2[N]; int dep[N], fa[N][20]; inline void dfs(int x, int father) { fa[x][0] = father; dep[x] = dep[father] + 1; F(i, 1, 19) fa[x][i] = fa[fa[x][i - 1]][i - 1]; F(i, 0, (int) e[x].size() - 1) { int y = e[x][i]; if (y == father) continue; dfs(y, x); } } inline int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); U(i, 19, 0) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i]; if (x == y) return x; U(i, 19, 0) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0]; } inline int getdis(int x, int y) { return dep[x] + dep[y] - (dep[lca(x, y)] << 1); } int sta[N], top, Fa[N], vis[N], siz[N], hev[N]; inline void getrt(int x, int father) { sta[++top] = x; siz[x] = 1; hev[x] = 0; F(i, 0, (int) e[x].size() - 1) { int y = e[x][i]; if (y == father || vis[y]) continue; getrt(y, x); siz[x]+= siz[y]; hev[x] = max(hev[x], siz[y]); } } inline void calc(int rt, int x, int father, int len) { dis1[rt].add(len, a[x]); F(i, 0, (int) e[x].size() - 1) { int y = e[x][i]; if (y == father || vis[y]) continue; calc(rt, y, x, len + 1); } } inline void dotdc(int x, int father) { top = 0; getrt(x, 0); int rt = -1; F(i, 1, top) hev[sta[i]] = max(hev[sta[i]], top - siz[sta[i]]); F(i, 1, top) if (rt == -1 || hev[sta[i]] < hev[rt]) rt = sta[i]; x = rt; Fa[x] = father; vis[x] = 1; dis1[x].build(top); dis2[x].build(top); if (father) F(i, 1, top) dis2[x].add(getdis(father, sta[i]), a[sta[i]]); F(i, 0, (int) e[x].size() - 1) { int y = e[x][i]; if (vis[y]) continue; calc(x, y, x, 1); dotdc(y, x); } } inline void modify(int x, int k) { int y = x; while (Fa[y]) { int dis = getdis(Fa[y], x); dis2[y].add(dis, k - a[x]); y = Fa[y]; dis1[y].add(dis, k - a[x]); } a[x] = k; } inline int query(int x, int k) { int y = x, res = a[x] + dis1[x].ask(k); while (Fa[y]) { int dis = getdis(Fa[y], x); if (dis <= k) res+= a[Fa[y]] + dis1[Fa[y]].ask(k - dis) - dis2[y].ask(k - dis); y = Fa[y]; } return res; } int main() { read(n), read(m); int opt, x, y; F(i, 1, n) read(a[i]); F(i, 2, n) read(x), read(y), e[x].pbk(y), e[y].pbk(x); dfs(1, 0); dotdc(1, 0); F(i, 1, m) { read(opt), read(x), read(y); x^= ans, y^= ans; if (opt) modify(x, y); else write(ans = query(x, y)), putchar(0xa); } return 0; }- [HNOI2015]开店
- P6329【模板】点分树 | 震波