入门点分治复杂度假了求助（TLE on #8，#9）

代码比较长，但是是模板，写法比较清真捏。

//Author: Velvet on Luogu(uid=443675)
#include <bits/stdc++.h>
#define int long long
#define mkpr make_pair
#define fi first
#define se second
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
using namespace __gnu_cxx;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(int x){write(x);putchar('\n');}
inline void writesp(int x){write(x);putchar(' ');}
inline int lowbit(int x) {return x&(-x);}
typedef pair<int,int> Pair;
const int N=100005,M=(N>>1);
int n,m,ask[105],ans[105];
int tot,head[M],nxt[M],to[M],w[M];
inline void add(int x,int y,int z){
    to[++tot]=y;w[tot]=z;nxt[tot]=head[x];head[x]=tot;
}
int siz[N],mx[N],usd[N],root,sum;
void calcsiz(int p,int fa){
    siz[p]=1;mx[p]=0;
    for(int i=head[p];i;i=nxt[i]){
        if(to[i]!=fa&&!usd[to[i]]){
            calcsiz(to[i],p);
            siz[p]+=siz[to[i]];
            mx[p]=max(mx[p],siz[to[i]]);
        }
    }
    mx[p]=max(mx[p],sum-siz[p]);
    if(mx[p]<mx[root]) root=p;
}
int d[N],dis[N],cnt;
void dfs(int p,int fa){
    d[++cnt]=dis[p];
    for(int i=head[p];i;i=nxt[i]){
        if(to[i]!=fa&&!usd[to[i]]){
            dis[to[i]]=dis[p]+w[i];
            dfs(to[i],p);
        }
    }
}
int hav[10000005];
void calc(int rt){
    hav[0]=1;queue<int> Q;Q.push(0);
    for(int i=head[rt];i;i=nxt[i]){
        cnt=0;
        dis[to[i]]=w[i];
        dfs(to[i],rt);
        F(j,1,cnt)F(k,1,m)
            if(ask[k]>=d[j]) ans[k]|=hav[ask[k]-d[j]];
        F(j,1,cnt){
            if(d[j]<=1e7) {
                hav[d[j]]=1;
                Q.push(d[j]);
            }
        }
    }
    while(Q.size()) hav[Q.front()]=0,Q.pop();
}
void dfz(int rt){
    calc(rt); usd[rt]=1;
    for(int i=head[rt];i;i=nxt[i]){
        if(!usd[to[i]]){
            root=0;
            mx[0]=sum=siz[to[i]];
            calcsiz(to[i],-1);calcsiz(root,-1);
            dfz(root); 
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    F(i,1,n-1){
        int u,v,w; cin>>u>>v>>w;
        add(u,v,w);add(v,u,w);
    }
    F(i,1,m) cin>>ask[i];
    mx[0]=sum=n;
    calcsiz(1,-1);
    calcsiz(root,-1);
    dfz(root);
    F(i,1,m) puts(ans[i]?"AYE":"NAY");
    return 0;
}