点分治

点分治，每次先找到当前联通块的重心，然后以重心为当前联通块的根节点，枚举并遍历根节点的一个子树，子树中的每个节点到根节点产生一条路径，如果这条路径的长度为 $x$，则在数据结构中查询此前被遍历过的子树中是否存在长度为 $k-x$ 的路径。

遍历完成后将当前子树的信息加入数据结构，这里用一个数组维护就行。不能边遍历子树边修改数据结构，这样会导致同一子树内节点的累加出不存在的路径长度。记录数组中哪些位置被使用，清空时只情空这些位置，否则时间复杂度是错误的。

由于以重心为根时，重心的最大孩子节点大小不超过整棵树节点数量的一半，执行一轮分治后树上连通块的大小至少减少到原先的二分之一，在 $O(\log n)$ 轮后连通块大小归零。由于一个点至多被遍历到 $O(\log n)$ 次，时间复杂度 $O(n \log n)$。

共有 $m$ 次询问，总体时间复杂度 $O(nm \log n)$。

#include<bits/stdc++.h>
using namespace std;
struct Star{int w,to;Star(int x,int y):w(x),to(y){}};
constexpr int lim=10'000'005;
int n,m,q[105],w[10'005],wson[10'005];
bool ans[105],on[10'005];
vector<int> sta,res,path;
vector<Star> v[10'005];
bitset<10'000'005> s;
void fisdfs(int x,int las){
    w[x]=1,wson[x]=0,sta.push_back(x);
    for(auto i:v[x]) if(i.to!=las&&!on[i.to]){
        fisdfs(i.to,x),w[x]+=w[i.to];
        if(w[i.to]>w[wson[x]]) wson[x]=i.to;
    }
}
void dfs(int x,int las,int dep){
    res.push_back(dep),path.push_back(dep);
    for(int i=1;i<=m;i++) if(dep<=q[i]&&s[q[i]-dep]) ans[i]=1;
    for(auto i:v[x]) if(i.to!=las&&!on[i.to]) dfs(i.to,x,dep+i.w);
}
void dfz(int x){
    sta.clear(),res.clear(),fisdfs(x,0);
    int ro=0;
    for(int i:sta) if(max(w[wson[i]],w[x]-w[i])*2<=w[x]) ro=i;
    on[ro]=1;
    for(auto i:v[ro]) if(!on[i.to]){
        path.clear(),dfs(i.to,0,i.w);
        for(int j:path) if(j<=lim) s[j]=1;
    }
    for(int i:res) if(i<=lim) s[i]=0;
    for(auto i:v[ro]) if(!on[i.to]) dfz(i.to);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;i++){
        static int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        v[x].push_back(Star(w,y));
        v[y].push_back(Star(w,x));
    }
    for(int i=1;i<=m;i++) scanf("%d",&q[i]);
    s[0]=1,dfz(1);
    for(int i=1;i<=m;i++){
        if(ans[i]) cout<<"AYE"<<'\n';
        else cout<<"NAY"<<'\n';
    }
    return 0;
}