点分治

zhy137036 · 2022-01-19 18:38:03 · 个人记录

点分治

例题

• 我们找一个点 r，并将树被分成若干份，每份是 r 的一个子树。

• 这样，长度为 k 的路径要么在 r 的一个子树里，要么经过 r。

  • 考虑前者，我们使用递归的方式求解（这就是为什么这个算法叫分治）。

  • 考虑后者。经过 r 的路径要么以 r 为端点，要么不以 r 为端点。不以 r 为端点的路径可以分成两个以 r 为端点的路径。

  • 我们开一个桶 xst[i]（取自“存在”的英文"exist"），表示是否存在一个结点，使它到 r 的距离为 i。

  • 剩下的工作就挺 naive 了吧。设 dep[u] 表示 u 到 r 的距离，设查询的路径长度为 q。

    • 对于 r 的每个子树，先遍历它的每个结点 u，看 xst[q-dep[u]] 是否为真；然后用这棵子树更新 xst 数组。
    • 注意因为是递归，所以 r 的子树处理完后要清空桶。暴力清空复杂度爆炸，应该将修改的位置存到栈里，对着栈清。

• 大常数。

  • 我们发现，每次递归的时候，找到的重心都是一样的，那为什么不提前存好重心呢。
  • 这样，我们以原无根树为基础，建出一棵新的有根树，叫点分树。
  • 整棵树的重心是点分树的根。重心的各个子树的重心作为点分树的根的子结点。以此类推。
  • 先建一棵点分树，然后直接在点分树上求解即可降低常数。

• 代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,qst,fcs,rot,siz[N],dep[N];
//qst是查询的路径长度
//fcs是临时的重心
//rot是全树的重心
//siz是子树大小
//dep是结点深度
int top,stk[N];
//保存修改痕迹的栈
vector<int>edge[N],wei[N],son[N];
//edge保存原树
//wei保存原树中边的长度
//son保存点分树
bool vis[N],xst[10000010];
//为了防止分治时跨出范围，用vis标记
//xst是桶
void getsize(int u,int fa){
//计算子树大小
    siz[u]=1;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(vis[v]||v==fa) continue;
        getsize(v,u);
        siz[u]+=siz[v];
    }
}
void getfcs(int u,int fa,int sum){
//计算重心（fcs取自“重心”的英文"focus"）
    int mx=0;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(vis[v]||v==fa) continue;
        mx=max(mx,siz[v]);
        getfcs(v,u,sum);
    }
    mx=max(mx,sum-siz[u]);
    if(mx<=sum/2) fcs=u;
}
void work(int u){
//建立点分树
    vis[u]=1;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(vis[v]) continue;
        getsize(v,u);
        getfcs(v,u,siz[v]);
        son[u].push_back(fcs);
        work(fcs);
    }
    vis[u]=0;
}
bool check(int u,int fa){
    if(dep[u]>qst) return 0;
    if(xst[qst-dep[u]]) return 1;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(vis[v]||v==fa) continue;
        dep[v]=dep[u]+wei[u][i];
        if(check(v,u)) return 1;
    }
    return 0;
}
void update(int u,int fa){
//更新桶
    if(dep[u]>qst) return;
    xst[dep[u]]=1;
    stk[++top]=dep[u];
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(vis[v]||v==fa) continue;
        update(v,u);
    }
}
bool solve(int u){
//回答查询
    bool re=0;
    vis[u]=1;
    for(int i=0;i<son[u].size();i++)
        if(solve(son[u][i])) { re=1; goto end; }
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(vis[v]) continue;
        dep[v]=wei[u][i];
        if(check(v,u)) { re=1; goto end; }
        update(v,u);
    }
    end:while(top) xst[stk[top--]]=0;
    vis[u]=0;
    return re;
}
int main(){
    xst[0]=1;
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w;
        edge[u].push_back(v);
        edge[v].push_back(u);
        wei[u].push_back(w);
        wei[v].push_back(w);
    }
    getsize(1,0);
    getfcs(1,0,n);
    rot=fcs;
    work(rot);
    for(int i=1;i<=m;i++){
        cin>>qst;
        cout<<(solve(rot)?"AYE":"NAY")<<endl;
    }
    return 0;
}