树分治

-1 前言

很久之前就该学会但是一直拖到现在才解决的东西。

看来真实的是有不少的更需要去填了。

0 前置芝士

• 树的重心
• 分治思想

1 何以为？

最早碰见这个东西实在2025年暑假北京MX集训的一场模拟赛中，当时T4是个点分治，坐我前面的前面的老哥打完说他AK了/bx/bx/bx。后来在各种比赛的题目中也常常见到这个东西，但由于一直咕咕咕没学就一直打暴力。直到现在才有时间来认真填一填坑。

点分治本质上就是对一般暴力的优化。一般统计树上信息的某些算法暴力地对每个点去做是 $O(n^2)$ 的，这很不好。点分治的原理就是利用了树的重心的性质（最大子树大小不超过 $\lfloor\frac{n}{2}\rfloor$），调整枚举顺序从而保证尽可能少的重复统计。

2 原理

2.1 点分治

下文以 P3806 【模板】点分治 为例。

很无脑的暴力做法是：枚举两个点，跳LCA去查询路径权值，时间复杂度 $O(n^2\log n)$。

这样很不好。我们考虑通过一些更高效的方式预处理出来出现过的权值。发现对于路径 $(u,v)$，可以枚举其 $LCA(u,v)=x$，任意一条路径 $(u,v)$ 都是由 $(u,x)$ 和 $(x,v)$ 两条路径拼接而成。所以一个新的做法是：枚举到点 $u$，计算所有子树内的点 $v$ 到点 $u$ 的距离 $dis_{u,v}$，然后逐一判断是否能合并出来询问中的数，这可以用一个桶来实现。时间复杂度 $O(nmk)$，其中 $k=\max_{i=1}^{n}dep_i$。

发现这个东西的时间复杂度甚至不如上面的无脑暴力。但是它的瓶颈很容易发现：我们发现每个点 $u$ 都被统计了 $dep_u$ 次，其中的很多显然是重复统计。

我们这么考虑：每当枚举完成一个点后，这个点本身就不再有用了。那么等价于把这个点从树上删去，对于剩下的部分形成的森林再依次求解，重复以上步骤。不难发现，如果让分出来的子树大小尽可能均等，复杂度很容易降到 $O(\log n)$ 级别。那么在一棵树上，去掉一个点，最坏情况下显然只会分成 $2$ 个部分。那么选取哪个点可以让分出来的两个部分尽可能小呢？没错，就是树的重心。

那么做法就变成了这样：每次都先找当前枚举到的这颗子树的重心，先对重心计算贡献，然后沿重心分开成若干部分再分别求解。由于每次子树的大小至少减半，所以每个点被统计一定不超 $O(\log n)$ 次，所以时间复杂度 $O(nm\log n)$，可以通过本题。

3 实现

按照我个人习惯，原理和代码分开放。

3.1 点分治

有几个常见的小问题：

• Q：树的重心怎么快捷好写地求出来？
• A：虽然平常多用二次扫描的方法，但是这里考虑“树的重心保证最大子树最小”，然后就可以求了。

主要代码如下：

struct node{
    int to,val;
};
std::vector<node> g[N];
int n,q;
int rt,sum;//当前子树的重心和当前子树的大小
int siz[N],dep[N],maxx[N];
int ans[N<<7],qry[N];
bool vis[N];//打过vis的点就相当于从树上删去了
void getrt(int u,int fa){//求重心
    maxx[u]=0;siz[u]=1;
    for(auto &i:g[u]){
        if(vis[i.to]||i.to==fa)continue;
        getrt(i.to,u);
        siz[u]+=siz[i.to];
        maxx[u]=std::max(maxx[u],siz[i.to]);
    }
    maxx[u]=std::max(maxx[u],sum-siz[u]);
    if(maxx[u]<maxx[rt])rt=u;
}
int dis[N];//子树内每个点到rt的距离
std::vector<int> dist;//当前扫描的这个子树各个点到根的距离(相当于上面的dis[]整理到一起了)
void getdis(int u,int fa){
    if(dis[u]>1e7)return;
    dist.push_back(dis[u]);
    for(auto &i:g[u]){
        if(i.to==fa||vis[i.to])continue;
        dis[i.to]=dis[u]+i.val;
        getdis(i.to,u);
    }
}
int bs[N<<7];//桶
std::vector<int> clr;//需要清空的位置
void calc(int u){
    clr.push_back(0);
    for(auto &i:g[u]){
        if(vis[i.to])continue;
        dis[i.to]=i.val;
        getdis(i.to,u);
        for(auto &j:dist){
            for(int k=1;k<=q;++k){
                if(qry[k]>=j)ans[k]|=bs[qry[k]-j];//能否通过当前i.to子树和前面已经枚举过的子树里面合并出来qry[k]的值
            }
        }
        for(auto &j:dist)clr.push_back(j),bs[j]=1;
        //注意这里要先算答案再把当前子树的dis添加进前面算完的子树里面，原因自己手玩一下就出来了
        dist.clear();
    }
    for(auto &j:clr){bs[j]=0;}
    clr.clear();
}
void solve(int u){
    vis[u]=1;bs[0]=1;calc(u);
    for(auto &i:g[u]){
        if(vis[i.to])continue;
        sum=siz[i.to];
        rt=0;maxx[0]=n;//注意这里一定要初始化rt和maxx[0]
        getrt(i.to,0);
        solve(rt);
    }
}
signed main(){
    n=read();q=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read(),w=read();
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(int i=1;i<=q;++i)qry[i]=read();
    maxx[rt]=n;
    sum=n;rt=0;//这里也是
    getrt(1,0);
    solve(rt);
    for(int i=1;i<=q;++i){
        printf(ans[i]?"AYE":"NAY");
        puts("");
    }
    return 0;
}

4 后记

后来有一天 能再见面 不知是何年