【算法专题】分治

点分治与点分树

https://oi-wiki.org/graph/tree-divide/

点分治：
按重心划分子树。

1. 在子树内部处理
2. 归并子树

AcWing 252. 树

https://www.acwing.com/problem/content/254/

1. 两点在同一子树内
2. 某点是重心
3. 两点不在同一子树内，路径经过重心（容斥删去不合法路径）

等价于给一堆数，任取两个数总和小于等于k的方案数是多少。
（重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。）

代码：嗨多细节

#include <bits/stdc++.h>

using namespace std;
const int N = 1e4 + 5, M = N * 2;
int h[N], e[M], ne[M], w[M], idx;
bool vis[N]; //该点是否被删
int dis_all[N], dis_cur[N]; //重心到所有子树的距离,重心到当前子树的距离
int n, m;

void add (int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int getSize (int u, int fa) { //以u为根的子树大小
    if (vis[u])     return 0; 
    int sz = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)    continue;
        sz += getSize (j, u);
    }
    return sz;
}

int getCenter (int u, int fa, int allSize, int &ct) { //求重心
    if (vis[u])     return 0;
    int sum = 1, maxSize = 1; //u的子树的结点个数
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)    continue;
        int curSize = getCenter (j, u, allSize, ct);
        sum += curSize;
        maxSize = max (maxSize, curSize);
    }
    maxSize = max (maxSize, allSize - sum);
    if (maxSize <= allSize / 2)   ct = u; //不一定是重心,满足一半即可,保证logn
    return sum;
}

void getDis (int u, int fa, int dis, int &len) { //当前子树上所有点到根的距离
    if (vis[u])     return ;
    dis_cur[len++] = dis;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)    continue;
        getDis (j, u, dis + w[i], len); //dis + w[i]记得更新距离啊!!
    }
}

int count (int *a, int sz) { //a[]中选两点满足dis<=m
    sort (a, a + sz);
    int cnt = 0; //满足条件的点对个数
    for (int i = sz - 1, j = -1; i >= 0; i--) {
        while (j < i - 1 && a[i] + a[j + 1] <= m)   j++;
        j = min (j, i - 1); //j左i右
        cnt += j + 1;
    }
    return cnt;
}

int cal (int u) { //递归计算以u为根的答案
    if (vis[u])     return 0;
    getCenter (u, -1, getSize (u, -1), u);
    vis[u] = true; //删重心

    int len = 0, cnt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        int len_cur = 0; //当前子树大小
        getDis (j, -1, w[i], len_cur);
        cnt -= count (dis_cur, len_cur); //情况3: 容斥掉同一树内的点对

        for (int k = 0; k < len_cur; k++) {
            if (dis_cur[k] <= m)    cnt++; //情况2: 某点是重心
            dis_all[len++] = dis_cur[k];
        }
    }
    cnt += count (dis_all, len); //情况3: 不同子树间的点对
    for (int i = h[u]; ~i; i = ne[i])    cnt += cal (e[i]);
    return cnt;
}

int main () {
    while (cin >> n >> m, n || m) {
        memset (h, -1, sizeof h), idx = 0;
        memset (vis, false, sizeof vis);
        for (int i = 1; i < n; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add (a, b, c), add (b, a, c);
        }
        cout << cal (0) << endl;
    }
}

边分治

CDQ分治