点分树

_MengShang_ · 2024-12-28 17:45:19 · 个人记录

点分树

前置知识：
点分治，树状数组，线段树等。
大致思路：
把点分治的过程离线下来，
将当前分治到的树重心与上一层的树重心连边，得到重构后的点分树。
然后考虑问题在原树上所求，转到点分树后的特点，以及如何维护。

例题:

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]开店