点分治

询问树上距离为 k 的点对是否存在。

#include<bits/stdc++.h>
using namespace std;
const int MAX=20010;
const int inf=1.5e8;
int n,m,x,y,z,q[MAX],rt,siz[MAX],maxx[MAX],dis[MAX];
vector<pair<int,int> >g[MAX];
stack<int>tag;
bool tf[inf],ret[MAX],vis[MAX];
int sum,d[MAX],cnt;
inline int read(){
    int x=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x;
} 
void zx(int,int);
void csiz(int,int);
void cdis(int,int);
void dfs(int,int);
int main(){
    n=read();m=read();
    for(int i=1;i<n;++i){
        x=read();y=read();z=read();
        g[x].push_back(make_pair(y,z));
        g[y].push_back(make_pair(x,z));
    }for(int i=1;i<=m;++i)  q[i]=read();
    maxx[rt=0]=MAX;sum=n;tf[0]=1;tag.push(0);
    zx(1,-1);csiz(rt,-1);dfs(rt,-1);
    for(int i=1;i<=m;++i)
        if(ret[i])  printf("AYE\n");
        else  printf("NAY\n");
}
void zx(int u,int fa){
    siz[u]=1;maxx[u]=0;
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i].first;
        if(v!=fa&&!vis[v]){
            zx(v,u);siz[u]+=siz[v];
            maxx[u]=max(maxx[u],siz[v]);
        }
    }maxx[u]=max(maxx[u],sum-maxx[u]);
    if(maxx[u]<maxx[rt])  rt=u;
}void csiz(int u,int fa){
    siz[u]=1;
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i].first;
        if(v!=fa&&!vis[v]){
            csiz(v,u);siz[u]+=siz[v];
        }
    }
}void cdis(int u,int fa){
    d[++cnt]=dis[u];
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i].first;
        if(v!=fa&&!vis[v]){
            dis[v]=dis[u]+g[u][i].second;cdis(v,u);
        }
    }
}
void dfs(int u,int fa){
    vis[u]=1;
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i].first;
        if(v!=fa&&!vis[v]){
            dis[v]=g[u][i].second;
            cnt=0;cdis(v,u);
            for(int j=1;j<=cnt;++j)
                for(int k=1;k<=m;++k)
                    if(q[k]>=d[j])  ret[k]|=tf[q[k]-d[j]];
            for(int j=1;j<=cnt;++j)  tag.push(d[j]),tf[d[j]]=1;
        }
    }while(tag.top())  tf[tag.top()]=0,tag.pop();
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i].first;
        if(v!=fa&&!vis[v]){
            maxx[rt=0]=MAX;sum=siz[v];
            zx(v,u);csiz(rt,-1);dfs(rt,-1);
        }
    }
}