往期浏览

树上分治

点分治

讲解

每次选取树的重心进行递归分治，中阶算法，大部分模板不需要理解，但是每一题都需要对维护函数进行修改。复杂度 \(\mathcal O(N\log N)\) 。

个人封装

由于需要进行一定程度的修改，不符合结构体封装的原则，故没有使用结构体。

int root = 0, MaxTree = 1e18; //分别代表重心下标、最大子树大小
vector<int> vis(n + 1), siz(n + 1);
auto get = [&](auto self, int x, int fa, int n) -> void { // 获取树的重心
    siz[x] = 1;
    int val = 0;
    for (auto [y, w] : ver[x]) {
        if (y == fa || vis[y]) continue;
        self(self, y, x, n);
        siz[x] += siz[y];
        val = max(val, siz[y]);
    }
    val = max(val, n - siz[x]);
    if (val < MaxTree) {
        MaxTree = val;
        root = x;
    }
};

auto clac = [&](int x) -> void { // 以 x 为新的根，维护询问
    
};

auto dfz = [&](auto self, int x, int fa) -> void { // 点分治
    vis[x] = 1; // 标记已经被更新过的旧重心，确保只对子树分治
    clac(x);
    for (auto [y, w] : ver[x]) {
        if (y == fa || vis[y]) continue;
        MaxTree = 1e18;
        get(get, y, x, siz[y]);
        self(self, root, x);
    }
};

get(get, 1, 0, n);
dfz(dfz, root, 0);

题单

1. 321C - Ciel the Commander：思路启蒙题，分治寻找重心；
2. P3806 【模板】点分治1：洛谷模板题；
3. P2634 [国家集训队] 聪聪可可：洛谷另一道模板题，与上一题几乎一致;