分治（一）

基本分治

分治的基本思想是：将一个问题分成若干个子问题，对每个子问题进行求解，再将所有子问题的解合并得到问题的解。
我们通过一个简单实用的例子来说明该类算法的思想。

归并排序

尽管我们几乎不会手写归并排序，但其思想对分治的理解是很有帮助的。
考虑我们需要排序的序列[1,n]，如果其子序列[1,mid]和[mid+1,r]都是有序的，我们怎么做才能将其合并成一个有序序列呢？
我们用两个指针分别遍历两个子序列，每次将两个指针指向的元素中较小的那个元素加入新的序列，最终得到的序列就是有序的。
于是我们的分治策略就出来了，对于序列[l,r]，先将其分成两半分别进行排序，再进行合并。
显然合并操作每一层总时间是O(n)的，而每次将序列分半，最多分$\log n$次，所以总复杂度为$O(n\log n)$。
这里我们就将合并一个序列的问题变成合并两个子序列的子问题，再将两个排好序的子序列进行合并，就得到了最终的有序序列。

void merge(int l, int r) {
    if (l == r)return;//只有一个元素当然是有序的
    int mid = l + r >> 1;
    merge(l, mid); merge(mid + 1, r);//分成两个序列，进行排序
    int i = l, r = mid + 1, tot = l - 1;
    while (i <= mid && j <= r) {
        if (a[i] < a[j])
            b{++tot] = a[i++];
        else
            b[++tot] = a[j++];
    }
    while (i <= mid)b[++tot] = a[i++];
    while (j <= r)b[++tot] = a[j++];//将其余元素放入当前序列
    for (int i = l; i <= r; ++i)a[i] = b[i];
}

树分治

点分治

现在，我们要对一棵树进行基于点的分治，首先选择一点作为当前无根树的根，将无根树化为有根树，再去递归地处理每一个与根连接的子树。
那么问题来了，如何选点呢？显然，我们希望递归的层数尽量少，自然不能胡乱选点。在点分治中我们选择一棵树的重心作为根。
何为重心？即将某个点删去后，剩余节点数量最多的树点的数量最少，则该点称为重心。
重心可以DP求解，复杂度$O(n)$：
dfs求得每个子树大小，选取一个根x删掉后，剩余树中节点最大值为$\max\{sz[y_1],sz[y_2],…,sz[y_n],sum-sz[x]\}$，从所有x中选择该最大值最小的节点作为根。

void getrt(int x, int fa) {
    sz[x] = 1; maxn[x] = 0;
    for (int e = p[x]; e; e = nt[e]) {
        int k = b[e];
        if (k == fa || vis[k])continue;
        getrt(k, x);
        sz[x] += sz[k];
        maxn[x] = max(maxn[x], sz[k]);
    }
    maxn[x] = max(maxn[x], sum - sz[x]);
    if (maxn[rt] > maxn[x])rt = x;
}

那么，知道了如何找根，分治的过程怎么写呢？
参考下面的模板

void solve(int x) {
    vis[x] = true;//我们用vis来标记已经搜过的根，以此来确定子树的边界
    ...
    calc(x);//处理x处，也就是当前子树的答案
    for (int e = p[x]; e; e = nt[e]) {
        int k = b[e];
        if (vis[k])continue;
        sum = sz[k];
        maxn[0] = INF;
        rt = 0;
        getrt(k, 0);//找到k子树中合适的根
        solve(rt);//分治
    }
}

至于其中的calc怎么写，根据题目会有变化。

边分治