点分治的一堆玩意

点分治，顾名思义，就是对每一个点进行分治操作。

一般是用来求树上距离的有关问题（目前是这样的）

首先以一道例题来讲解点分治的基本操作。

P3806

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

暴力是的，然后就会发现你 TLE 了。

考虑点分治。

点分治的基本思想是：我们对于每一个点，可以通过枚举他的子树来枚举所有经过这个点的边，然后计算答案。之后再把以这个节点为根的子树分成两个子树，继续分治。这样的复杂度就变为了。

而分治肯定是尽量把他分成两个大小差不多的子树，所以这个点就要设为这棵树的重心。

我们怎么枚举经过这个点的所有边呢？我们可以一个子树一个子树的看：

我们存储一个桶 nowhave，表示之前遍历过的点到这个距离。就是如果这个距离在之前遍历过的子树存在的话，就设的值为。然后这个子树的所有点到根的距离用一个数组 nowdis 存。然后我们开始遍历这个数组。如果，那么就说明树上存在距离为的点对。

然后这个点分治完了之后，就可以去分治子树了。我们继续找到子树上的重心，然后向之前一样继续分治，然后再找子树的重心的子树……直到把所有点都分治完。然后就可以得到答案。

主要用到了个函数：

获取该树重心：

void getzx(int x, int fa){ //get 重心
    siz[x] = 1;
    maxsiz[x] = 0;
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(v==fa||vis[v]) continue;
        getzx(v, x);
        siz[x] += siz[v];
        maxsiz[x] = max(maxsiz[x], siz[v]);
    }
    maxsiz[x] = max(maxsiz[x], nown - siz[x]);
    if(maxsiz[x] < maxsiz[rt]) rt = x;
}

获取该节点的子树到该节点的距离集合：

void getdis(int x, int fa){
    if(dis[x] > MAXNUM) return ;
    nowtrdis[++len] = dis[x];
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(v==fa||vis[v]) continue;
        dis[v] = dis[x] + edge[i].w;
        getdis(v, x);
    }
}

对某一个点分治：

void eachsolve(int x){
    int tmpcnt = 0;
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(vis[v]) continue;
        len = 0, dis[v] = edge[i].w;
        getdis(v, x);
        for(int j=1;j<=len;j++){
            for(int k=1;k<=q;k++){
                if(que[k] >= nowtrdis[j]){
                    ans[k] |= (nowhave[que[k]-nowtrdis[j]]);
                }
            }
        }
        for(int j=1;j<=len;j++){
            tmp[++tmpcnt] = nowtrdis[j];
            nowhave[nowtrdis[j]] = 1;
        }
    }
    for(int i=1;i<=tmpcnt;i++){
        nowhave[tmp[i]] = 0;
    }
}

对所有点进行分治：

void solve(int x){
    vis[x] = 1;
    nowhave[0] = 1;
    eachsolve(x);
    // cout<<"! "<<x<<'\n';
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(vis[v]) continue;
        maxsiz[0] = n;
        nown = siz[v];
        rt = 0;
        getzx(v, x);
        solve(rt);
    }
}

Tips:

主函数要先设置nown = n; maxsiz[0] = n; rt = 0;！！！初始化要记得有！

然后再 getzx(1,0); solve(rt);

最后输出答案。

注意当 dis > k 的时候要剪枝！！不然会 RE 或 TLE！

该题 Code：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+4;
struct Edge{
    int to, nxt, w;
}edge[N<<1];
int h[N], cnt;
void _add(int u, int v ,int w){
    edge[++cnt] = {v, h[u], w};
    h[u]  = cnt;
}
void add(int u, int v, int w){
    _add(u, v, w), _add(v, u, w);
}

int vis[N];
int rt=0, n, q;
int siz[N];
int maxsiz[N];
int nown;
void getzx(int x, int fa){ //get 重心
    siz[x] = 1;
    maxsiz[x] = 0;
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(v==fa||vis[v]) continue;
        getzx(v, x);
        siz[x] += siz[v];
        maxsiz[x] = max(maxsiz[x], siz[v]);
    }
    maxsiz[x] = max(maxsiz[x], nown - siz[x]);
    if(maxsiz[x] < maxsiz[rt]) rt = x;
}
int nowtrdis[N];
int len = 0;
int dis[N];
const int MAXNUM = 1e7;
void getdis(int x, int fa){
    if(dis[x] > MAXNUM) return ;
    nowtrdis[++len] = dis[x];
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(v==fa||vis[v]) continue;
        dis[v] = dis[x] + edge[i].w;
        getdis(v, x);
    }
}
const int MAXN = 1e7+5;
bool ans[105];
bool nowhave[MAXN];
int que[105];
int tmp[N];
void eachsolve(int x){
    int tmpcnt = 0;
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(vis[v]) continue;
        len = 0, dis[v] = edge[i].w;
        getdis(v, x);
        for(int j=1;j<=len;j++){
            for(int k=1;k<=q;k++){
                if(que[k] >= nowtrdis[j]){
                    ans[k] |= (nowhave[que[k]-nowtrdis[j]]);
                }
            }
        }
        for(int j=1;j<=len;j++){
            tmp[++tmpcnt] = nowtrdis[j];
            nowhave[nowtrdis[j]] = 1;
        }
    }
    for(int i=1;i<=tmpcnt;i++){
        nowhave[tmp[i]] = 0;
    }
}

void solve(int x){
    vis[x] = 1;
    nowhave[0] = 1;
    eachsolve(x);
    // cout<<"! "<<x<<'\n';
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(vis[v]) continue;
        maxsiz[0] = n;
        nown = siz[v];
        rt = 0;
        getzx(v, x);
        solve(rt);
    }
}
int main(){
    // freopen("P3806_1.in", "r", stdin);
    // freopen("P3806.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>q;
    nown = n;
    maxsiz[0] = n;
    int u, v, w;
    for(int i=1;i<n;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    for(int i=1;i<=q;i++){
        cin>>que[i];
    }
    rt = 0;
    getzx(1,0);
    solve(rt);
    for(int i=1;i<=q;i++){
        cout<<(ans[i]?"AYE\n":"NAY\n");
    }
    return 0;
}

P4178

这道题和之前的做法比较不一样。还是先找点然后分治。然后就是 eachsolve 函数里面要改一下。

这个函数还是先把所有的边都遍历一遍。然后我们要设置一个 color 数组，将每一个子树的 color 染色染成同一种颜色，不同的子树，color 也是不同的。（特别的，分治点要单独赋一种颜色。）

于是我们就把这棵树染成了：根一个颜色，这个根连边到的每一个点的树一种颜色。这样就会有分治点的出度种颜色。

我们首先把这些距离都整合到一个数组里面，然后把这些按距离从小到大排序。然后就可以开始算距离的点对数了。

我们从左往右遍历，然后只要加起来（）值的都可以。所以我们可以求出一个极限值，就是并且。因为数组是递增的，所以会随着的增大而减小。所以每次遍历的时候就用 while 判一下。这样遍历的复杂度就是。

如果不考虑是否两个点在同一个子树的情况下，对于每一个，答案就是。但是有两个点在同一个子树的情况，所以就会有一些情况是非法的。所以我们就可以求出中间的颜色和一样的点的总数，那么答案就变成了。那么我们怎么才能把快速求出来呢？我们记录一个数组，表示当前区间的，每种颜色的总数。最开始先遍历一遍数组，然后把求出来。然后再让他随着和的更新而实时更新。就是当或者改变的时候，就让 $改变的那个地方$ 减。最后该节点答案就是。注意 f 数组是随着 i 和 j 的更新而实时更新的！

eachsolve 函数的代码：

int ans = 0;
void eachsolve(int x){
    tmpcnt = 0;
    tmp[++tmpcnt] = {0,x};
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(vis[v]) continue;
        len = 0;
        dis[v] = edge[i].w;
        getdis(v, x);
        for(int j=1;j<=len;j++){
            tmp[++tmpcnt] = {nowdis[j], v};
        }
    }
    sort(tmp+1, tmp+1+tmpcnt, cmp);
    for(int i=1;i<=tmpcnt;i++){
        f[tmp[i].col] ++;
    }
    for(int i=1,j=tmpcnt;i<=j;i++){
        while(tmp[i].dis + tmp[j].dis > k){
            f[tmp[j].col] --;
            j--;
        }
        if(i>j) break;
        ans += (j-i+1-f[tmp[i].col]);
        f[tmp[i].col] --;
    }
}

点分治的一堆玩意

P3806

P4149

P4178