点分治奇怪写法TLE#7#9求条

...，用动态开点线段树写得

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const int M=5e6+5;
const int K=1e7;
int n,m;
int edge[N*2],ver[N*2],head[N],nxt[N*2],tot;
void add(int u,int v,int w){
    edge[++tot]=w;
    ver[tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}
int k[N],ans[N];
bitset<N>dis;//已经被删除了的点
bitset<N>book;//在dfs中被标记过的点
int siz[N];//当前siz
int dsiz[N];//子树最大siz
vector< pair<int,int> >v;//它的长度和属于哪颗子树
int t[N];//前缀子树大小
int zx;//重心
void dfssiz(int u){
    book[u]=1;
    siz[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=ver[i];
        if(!dis[v]&&!book[v]){
            dfssiz(v);
            siz[u]+=siz[v];
        }
    }
    book[u]=0;
}
void dfszx(int u,int fa){
    book[u]=1;
    dsiz[u]=0;
    for(int i=head[u];i;i=nxt[i]){
        int v=ver[i];
        if(!dis[v]&&!book[v]){
            dfszx(v,fa);
            dsiz[u]=max(dsiz[u],siz[v]);
        }
    }
    dsiz[u]=max(dsiz[u],siz[fa]-siz[u]);
    if(dsiz[u]<dsiz[zx]){
        zx=u;
    }
    book[u]=0;
}
struct node{
    int l,r;
}tr[M];
int tot1;
int tc[M];
int New(int l,int r,int op){
    ++tot1;
    tr[tot1].l=l;
    tr[tot1].r=r;
    tc[tot1]=op;
    return tot1;
}
void update(int &p,int l,int r,int k,int x){
    if(p==0)p=New(0,0,0);
    if(l==r&&r==k){
        tc[p]+=x;
        return;
    }
    int mid=(l+r)>>1;
    if(k<=mid)update(tr[p].l,l,mid,k,x);
    else update(tr[p].r,mid+1,r,k,x);
}
int query(int& p,int l,int r,int k){
    if(p==0){
        return 0;
    }
    if(l==r&&r==k){
        return tc[p];
    }
    int mid=(l+r)>>1;
    if(k<=mid)return query(tr[p].l,l,mid,k);
    else return query(tr[p].r,mid+1,r,k);
}
int rt;
void dfsxds(int u,int sum,int x){
    if(sum>(int)(1e7)){
        return;
    }
    update(rt,1,K,sum,x);
    book[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        if(!dis[ver[i]]&&!book[ver[i]]){
            dfsxds(ver[i],sum+edge[i],x);
        }
    }
    book[u]=0;
}
bool booldfs(int u,int sum,int id){
    book[u]=1;
    ans[id]+=sum>k[id]?false:(sum==k[id]?true:query(rt,1,K,k[id]-sum)>0);
    if(ans[id]){
        book[u]=0;
        return ans[id];
    }
    if(sum>k[id]){
        book[u]=0;
        return false;
    }
    for(int i=head[u];i;i=nxt[i]){
        if(!dis[ver[i]]&&!book[ver[i]]){
            ans[id]+=booldfs(ver[i],sum+edge[i],id);
        }
        if(ans[id]){
            book[u]=0;
            return ans[id];
        }
    }
    book[u]=0;
    return ans[id];
}
void dfz(int u){
    dfssiz(u);  
    zx=0;
    dsiz[zx]=1e9;
    dfszx(u,u);
    book[zx]=1;
    for(int i=head[zx];i;i=nxt[i]){
        if(dis[ver[i]])continue;
        dfsxds(ver[i],edge[i],1);
    }
    for(int f=1;f<=m;f++){
        if(ans[f])continue;
        for(int i=head[zx];i;i=nxt[i]){
            if(dis[ver[i]])continue;
            dfsxds(ver[i],edge[i],-1);
            booldfs(ver[i],edge[i],f);
            dfsxds(ver[i],edge[i],1);
            if(ans[f])break;
        }
    }
    for(int i=head[zx];i;i=nxt[i]){
        if(dis[ver[i]])continue;
        dfsxds(ver[i],edge[i],-1);
    }
    book[zx]=0;
    dis[zx]=1;
    for(int i=head[zx];i;i=nxt[i]){
        if(!dis[ver[i]]){
            dfz(ver[i]);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=m;i++){
        cin>>k[i];
    }
    dfz(1);
    for(int i=1;i<=m;i++){
        if(ans[i]){
            cout<<"AYE\n";
        }else{
            cout<<"NAY\n";
        }
    }
    return 0;
}