树分治总结

panyf · 2021-04-05 20:57:45 · 个人记录

点分治

点分治用于解决树上路径问题。

适用范围：可以在较快时间（比如 O(n) 或 O(n\log n)）内求出经过某个点 x 的所有路径的信息。

算法流程：

每次选择当前树的重心 r 作为根节点，处理经过 r 的所有路径的信息。

然后对 r 的每一个子树递归处理。

复杂度证明：

由重心性质，每次递归子树大小至少减半，所以每个点只会在 \log 个子树中出现，总复杂度就是 O(n\log n)。

再考虑处理路径信息的复杂度，根据主定理，如果处理大小为 n 的子树复杂度是 O(n\log^k n)，总复杂度就是 O(n\log^{k+1}n)。如果是 O(n\sqrt n)，总复杂度还是 O(n\sqrt n)。

模板题：P3806 【模板】点分治1 提交记录

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+3,P=1e7+3;
int he[N],to[N*2],ne[N*2],len[N*2],st[N],sz[N],q[109],o,r,t,n,m;
bool ans[109],f[P],b[N];
void gr(int x,int y){//求重心
    int i=he[x],j,w=0;
    for(sz[x]=1;i;i=ne[i])if(!b[j=to[i]]&&j!=y)gr(j,x),sz[x]+=sz[j],w=max(w,sz[j]);
    if((w=max(w,n-sz[x]))<o)o=w,r=x;
}
void gd(int x,int y,int z){if(z<P&&(st[++t]=z))for(int i=he[x],j;i;i=ne[i])if(!b[j=to[i]]&&j!=y)gd(j,x,z+len[i]);}
void wk(int x){
    int i=he[x],j,k,l=0;
    for(b[x]=1;i;i=ne[i])if(!b[j=to[i]]){
        for(gd(j,x,len[i]),j=t;j>l;--j)for(k=1;k<=m;++k)if(q[k]>=st[j])ans[k]|=f[q[k]-st[j]];
        while(l<t)f[st[++l]]=1;
    }
    while(t)f[st[t--]]=0;
    for(i=he[x],l=n;i;i=ne[i])if(!b[j=to[i]])n=sz[x]>sz[j]?sz[j]:l-sz[x],o=N,gr(j,0),wk(r);
    //n是子树j的size，因为x和j在求sz时一定是父子关系，所以分两种情况讨论即可求出n
}
int main(){
    int i,j,k,l,t=0;
    scanf("%d%d",&n,&m);
    for(i=f[0]=1;i<n;++i)scanf("%d%d%d",&j,&k,&l),ne[++t]=he[j],to[t]=k,len[t]=l,he[j]=t,ne[++t]=he[k],to[t]=j,len[t]=l,he[k]=t;
    for(i=1;i<=m;++i)scanf("%d",q+i);
    for(o=N,gr(i=1,0),wk(r);i<=m;++i)puts(ans[i]?"AYE":"NAY");
    return 0;
}

习题：

P6626 [省选联考 2020 B 卷] 消息传递

P7518 [省选联考 2021 A/B 卷] 宝石

P5306 [COCI2019] Transport

P4183 [USACO18JAN]Cow at Large P

点分治统计答案常见方法