（动态）树分治

pldzy · 2022-06-16 14:09:57 · 个人记录

浅谈一下学了好久的树分治。

一、点分治

适合处理大规模树上路径信息问题。

P3806 【模板】点分治1

很基础的了，询问树上距离为 k 的点对是否存在。

大概就是每次找重心当作根，对于当前的根，统计每个子节点到它的距离，然后用双指针遍历，当且仅当两个儿子到当前根的距离之和为 k 且来自根的不同子树时，这两个子节点的距离就为 k，那么距离为 k 的点对存在。

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn = 1e4 + 5;
const int maxm = 105;
int n, m, q[maxm];
bool k[maxm], vis[maxn];
int cnt, hd[maxn];
struct node{
    int to, nxt, w;
}e[maxn << 1];
int a[maxn], tot, d[maxn], b[maxn], mxs[maxn], siz[maxn];
int rt;

inline void add(int u, int v, int w)
{
    e[++cnt].to = v;
    e[cnt].nxt = hd[u], hd[u] = cnt;
    e[cnt].w = w;
}

inline void getrt(int u, int fa, int sum)
{
    siz[u] = 1, mxs[u] = 0;
    for(int i = hd[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(vis[v] or v == fa) continue;
        getrt(v, u, sum);
        mxs[u] = max(mxs[u], siz[v]);
        siz[u] += siz[v];
    }
    mxs[u] = max(mxs[u], sum - siz[u]);
    if(!rt or mxs[rt] > mxs[u]) rt = u;
}

inline void getdis(int u, int fa, int dis, int anc)
{
    a[++tot] = u, d[u] = dis, b[u] = anc;
    for(int i = hd[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa or vis[v]) continue;
        getdis(v, u, dis + e[i].w, anc);
    }
}

inline bool cmp(int x, int y)
{
    return d[x] < d[y];
}

inline void clc(int u)
{
    tot = 0;
    /*
    记当前分治的根为 rootroot。
    a 数组记录从 root 能到的点;
    d 数组记录 ai 到 root 的距离;
    b 数组记录 ai属于 root 的哪一棵子树(即当 b[a[i]]=b[a[j] 时,说明 a[i]与 a[j]属于 rootroot 的同一棵子树)
    */
    a[++tot] = u, b[u] = u, d[u] = 0;
    for(int i = hd[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(vis[v]) continue;
        getdis(v, u, e[i].w, v);
    }
    sort(a + 1, a + tot + 1, cmp);
    rep(i, 1, m)
    {
        if(k[i]) continue;
        int l = 1, r = tot;
        while(l < r)
        {
            int w = d[a[l]] + d[a[r]];
            if(w < q[i]) l += 1;
            else if(w > q[i]) r -= 1;
            else if(b[a[l]] == b[a[r]])
                if(d[a[r]] == d[a[r - 1]]) r -= 1;
                else l += 1;
            else
            {
                k[i] = 1;
                break;
            }
        }
    }
}

inline void slv(int u)
{
    vis[u] = 1;
    clc(u);
    for(int i = hd[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(vis[v]) continue;
        rt = 0, getrt(v, 0, siz[v]);
        slv(rt);    
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    rep(i, 1, n - 1)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }
    rep(i, 1, m) 
    {
        scanf("%d", &q[i]);
        if(!q[i]) k[i] = 1;
    }
    mxs[0] = n;
    getrt(1, 0, n);
    slv(rt);
    rep(i, 1, m) 
        if(k[i]) printf("AYE\n");
        else printf("NAY\n");
    return 0;
}

另一道类似的升级题：P4178 Tree。

题意变为求出树上两点距离小于等于 k 的点对数量。思路差不多，不过是在遍历统计答案的时候使用双指针统计答案，即合法点对个数。但是要注意，如果只是单单这样，显然双指针会把这种情况统计进去：

（图自此博客。）

所以再套个容斥就好了。

code

二、动态点分治/点分树

感觉这个东西还是比较灵活的。

P6329 【模板】点分树 | 震波

所有与 x 距离不超过 k 的城市都将受到影响，求该次地震造成的经济损失，即所有受影响城市的价值和，待修改（修改某节点价值）。强制在线。

首先提出一个关于点分树的概念——重构树。即把当前树的重心和上一层的树重心连边，后者是前者父亲。这样得到的重构树形态优秀，有利于解决和树的形态无关的问题。

剩下具体怎么在重构树上查询距离、记录距离等等见此题解。

其中还用了一个 \mathcal{\text{O}}(1) 求 LCA 的小技巧。

特别要注意的一点是：我们再构造重构树之前就已经记录下原树上两个节点的距离了，后续题目不会再对树的形态进行改变了，所以方法可行。

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(register int i = a; i <= b; ++i)
#define go(u) for(int i = hd[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
const int maxn = 2e5 + 5;
const int inf = 1e9 +7;
int n, m;
int a[maxn], cnt, hd[maxn];
struct node{
    int to, nxt;
}e[maxn << 1];
int pos[maxn], id[maxn], tot;
int st[maxn << 1][21], dep[maxn], rt, sum;
int siz[maxn], fa[maxn], lg[maxn << 1];
bool vis[maxn];
int ans, mxx;
vector <int> c[2][maxn];

inline void add(int u, int v){
    e[++cnt] = (node){v, hd[u]};
    hd[u] = cnt;
}

inline void dfs1(int u, int f){
    st[++tot][0] = u, pos[u] = tot;
    go(u) if(v != f){
        dep[v] = dep[u] + 1, dfs1(v, u);
        st[++tot][0] = u;
    }
}

inline int minn(int a, int b){
    return dep[a] < dep[b] ? a : b;
}

inline void pre(){
    lg[0] = -1;
    rep(i, 1, tot) lg[i] = lg[i / 2] + 1;
    for(int k = 1; (1 << k) <= cnt; ++k)
        for(int i = 1; i + (1 << k) <= cnt; ++i)
            st[i][k] = minn(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}

inline void findrt(int u, int f){
    siz[u] = 1;
    int mxs = 0;
    go(u) if(v != f and !vis[v]){
        findrt(v, u), siz[u] += siz[v];
        mxs = max(mxs, siz[v]);
    }
    mxs = max(mxs, sum - mxs);
    if(!rt or mxs < mxx) rt = u, mxx = mxs;
}

inline void build(int u){
    vis[u] = 1, siz[u] = sum + 1;
    c[0][u].resize(siz[u] + 1), c[1][u].resize(siz[u] + 1);
    go(u) if(!vis[v]){
        sum = siz[v], rt = 0, mxx = -inf, findrt(v, u);
        fa[rt] = u, build(rt);
    }
}

inline int gdis(int u, int v){
    if(pos[u] > pos[v]) swap(u, v);
    int x = pos[u], y = pos[v], k = y - x + 1;
    int lca = minn(st[x][lg[k]], st[y - (1 << lg[k]) + 1][lg[k]]);
    return dep[u] + dep[v] - 2 * dep[lca];
}

inline int lb(int x){
    return x & (-x);    
}

inline void update(int u, int opt, int x, int w){
    x += 1;
    for(int i = x; i <= siz[u]; i += lb(i)) 
        c[opt][u][i] += w;
}

inline int query(int x, int opt, int y){
    y += 1;
    int res = 0;
    for(int i = min(y, siz[x]); i; i -= lb(i))
        res += c[opt][x][i];
    return res;
}

inline void update_path(int x, int w){
    for(int i = x; i; i = fa[i]) update(i, 0, gdis(x, i), w);
    for(int i = x; fa[i]; i = fa[i]) update(i, 1, gdis(x, fa[i]), w);
}

int main(){
    scanf("%d%d", &n, &m);
    rep(i, 1, n) scanf("%d", &a[i]);
    rep(i, 2, n){
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dep[1] = 1, dfs1(1, 0), pre();
    sum = n, mxx = -inf, findrt(1, 0), build(rt);
    rep(i, 1, n) update_path(i, a[i]);
    rep(i, 1, m){
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        x ^= ans, y ^= ans;
        if(!opt){
            ans = query(x, 0, y);
            for(int i = x; fa[i]; i = fa[i]){
                int dis = gdis(fa[i], x);
                if(y >= dis)
                    ans += query(fa[i], 0, y - dis) - query(i, 1, y - dis);
            }
            printf("%d\n", ans);
        }
        else update_path(x, y - a[x]), a[x] = y;
    }
    return 0;
}   

重构树的具体应用可以见下述的“动态树分治”。

三、动态树分治

模板：P4719 【模板】"动态 DP"&动态树分治

动态树分治，也叫动态 DP 问题，是猫锟在 WC2018 讲的黑科技，一般用来解决树上的带有点权（边权）修改操作的 DP 问题。