点分治总结

　　这几天学了学点分治

　　点分治是一种处理树上路径/点对的计数问题的高效算法，它的递归层数在logn之内

　　我们考虑如何对一棵树进行分治：因为要让递归层数尽可能的小，我们要选一个点，使得这个点的最大子树大小最小，即这棵树的重心，然后对路径进行处理，删去该点之后，关于剩下的几棵树进行分治

　　显然，这样的算法，递归层数最大是logn的

　　然后我们考虑如何对路径进行处理：因为不包含当前点的路径一定会在其它点的分治中处理到，因此我们只需要处理包含当前点的路径即可。既然这样，我们就可以像维护子树信息一样地维护通过当前点的路径了。我们维护f和g两个数组，分别表示当前子树的信息和已计算过的子树信息，我们只需要将f数组和g数组做相关的运算，最后将f数组加入到g数组中即可。全部处理完之后要记得将g数组清零

　　这样处理我们得到的是满足答案的所有无序的二元组，如果题目要求所有有序的二元组，将答案*2即可

　　代码大概是这样的：

void getroot(int x, int par) {//经典树形DP，找到当前树的重心
    size[x] = 1; maxsize[x] = 0;
    for (int i = lin[x], y; i; i = edge[i].ne) {
        if (vis[y = edge[i].y] || y == par) continue;
        getroot(y, x);
        size[x] += size[y];
        maxsize[x] = std::max(maxsize[x], size[y]);
    }
    maxsize[x] = std::max(maxsize[x], sum - size[x]);
    if (maxsize[x] < maxsize[root]) root = x;
}

void cal(int x, int par) {//计算当前子树对答案的贡献
    //处理当前节点和已计算的节点之间产生的贡献
    for (int i = lin[x], y; i; i = edge[i].ne) {
        if (vis[y = edge[i].y] || y == par) continue;
        //在递归到y之前处理y的相关信息
        cal(y, x);
    }
}

void add(int x, int par, bool flag) {
    //若flag为false，则将当前节点信息加入到已计算的节点的信息中，否则将已计算的节点的信息清零
    for (int i = lin[x], y; i; i = edge[i].ne) {
        if (vis[y = edge[i].y] || y == par) continue;
        add(y, x, flag);
    }
}

void solve(int x) {
    getroot(x);//找到重心之后，关于重心再做一遍DFS，得到所有点的size
    vis[x] = true;//删去当前点
    //将当前加入到已计算的节点的信息中
    for (int i = lin[x], y; i; i = edge[i].ne) {
        if (vis[y = edge[i].y]) continue;
        cal(y, x);
        add(y, x, false);
    }
    for (int i = lin[x], y; i; i = edge[i].ne) {
        if (vis[y = edge[i].y]) continue;
        add(y, x, true);
    }
    for (int i = lin[x], y; i; i = edge[i].ne) {
        if (vis[y = edge[i].y]) continue;
        sum = size[y];
        root = 0;
        getroot(y, 0);
        solve(root);
    }
}

　　有几个需要注意的点：

　　　　因为每次root都要重置为0，因此我们要让maxsize0是一个最大值。

　　　　第一次solve前需要让sum = n

　　　　注意检查分治时调用的变量是不是solve(root)

　　　　一定要先处理重心并删去重心

　　　　solve内不再getroot一次的话，与x相邻的点中有一个点的size是不正确的，这可能会导致复杂度的不正确