树分治系列：

• 点分治原理与实现 | KSkun’s Blog
• 边分治原理及实现 | KSkun’s Blog

概述

点分治是一种分治策略，其核心在于寻找树的重心，从重心分治解决，从而优化复杂度，实现O(\log n)的分治复杂度（不含分治中的处理复杂度）。

原理与实现

其实点分治的核心并不在于本篇文章介绍的内容，而是在于设计分治问题的思路上。因此本篇文章并没有多少内容。

找重心

分治的第一步是找到重心。树的重心指的是以该点为根的有根树的最大子树大小最小的点，这样的点满足其子树大小分布比较平衡，可以更好地缩小问题规模。在实际操作中，我们设计递归算法，将一个根的最大子树统计出来，注意其父亲的这一部分子树也要计入。

inline void getroot(int u, int fa) {
    siz[u] = 1; msz[u] = 0;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].to;
        if(vis[v] || v == fa) continue;
        getroot(v, u);
        siz[u] += siz[v];
        msz[u] = std::max(msz[u], siz[v]);
    }
    msz[u] = std::max(msz[u], sum - msz[u]);
    if(msz[u] < msz[rt]) rt = u;
}

处理问题的流程

既然是分治，我们就要考虑分治的流程。

1. 找到子树的重心，递归到子树重心去解决子问题
2. 将子树的答案合并至当前树根

例题：【P3806】【模板】点分治1 – 洛谷

题目描述

给定一棵有n个点的树，询问树上距离为k的点对是否存在。

分析

这个k我们可以拆成树上从根出发的两条链计算。考虑点分治处理。
对于一个根，我们统计其所有儿子到根的距离。这些距离本身可以作为答案，而如果儿子不在同一个子树内，那么两个儿子到根的路径还可以拼成一条长链，也作为答案。
复杂度分析：找重心O(n)，处理距离O(n)，计算答案O(n^2)。可以表示为T(n)=kT(\frac{n}{k})+O(n^2)，根据主定理，我们可以知道该算法的复杂度为O(n^2)。
诶说起来咋过的1e5啊，这个数据很玄学啊。
下面我们来讲O(n \log n)的写法，计算答案的拼接我们可以变成，找到一条路径，再二分查找是否存在加和为k的另外一条路径，这样做就可以O(n \log n)地统计答案，总复杂度也降下来了。然而我没写这种方法。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005, INF = 1e9;

int n, m, ut, vt, wt, k, rt;
int siz[MAXN], dep[MAXN], has[10000005], msz[MAXN], sum;
bool vis[MAXN];

struct Edge {
    int to, w;
};

std::vector<Edge> gra[MAXN];

struct Node {
    int dis, subt;
} ans[MAXN];
int atot = 0;

inline void getroot(int u, int fa) {
    siz[u] = 1; msz[u] = 0;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].to;
        if(vis[v] || v == fa) continue;
        getroot(v, u);
        siz[u] += siz[v];
        msz[u] = std::max(msz[u], siz[v]);
    }
    msz[u] = std::max(msz[u], sum - siz[u]);
    if(msz[u] < msz[rt]) rt = u;
}

inline void caldep(int u, int fa, int deep, int subt) {
    ans[atot++] = Node {dep[u], subt};
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].to, w = gra[u][i].w;
        if(vis[v] || v == fa) continue;
        dep[v] = dep[u] + w;
        if(deep != 1) caldep(v, u, deep + 1, subt);
        else caldep(v, u, deep + 1, v);
    }
}

inline void work(int u) {
    atot = 0;
    dep[u] = 0;
    caldep(u, 0, 1, -1);
    for(int i = 0; i < atot; i++) {
        for(int j = i + 1; j < atot; j++) {
            if(ans[i].subt != ans[j].subt) {
                has[ans[i].dis + ans[j].dis] = true;
            }
            has[ans[i].dis] = has[ans[j].dis] = true;
        }
    }
}

inline void dfs(int u) {
    work(u);
    vis[u] = true;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].to;
        if(vis[v]) continue;
        rt = 0;
        sum = siz[v];
        getroot(v, 0);
        dfs(rt);
    }
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint(); wt = readint();
        gra[ut].push_back(Edge {vt, wt});
        gra[vt].push_back(Edge {ut, wt});
    }
    rt = 0;
    msz[0] = INF;
    sum = n;
    getroot(1, 0);
    dfs(rt);
    while(m--) {
        k = readint();
        if(has[k]) puts("AYE"); else puts("NAY");
    }
    return 0;
}