桶

#include<bits/stdc++.h>
using namespace std;
int kn,N,n,k[23333],u,v,q,siz[41111],rot,mas,fa[41111],mi[41111],paint[41111],deep[41111],color_id;
int head[41111],last[41111],ans[23333],stackk[41111],dfn;
struct node {
    int to,next,val;
} s[233333];
void find_root(int x) {
    siz[x]=1,mi[x]=0;
    for(int i = head[x]; i != 0; i = s[i].next) {
        if(s[i].to==fa[x]) continue;
        if(paint[s[i].to]!=paint[x]) continue;
        fa[s[i].to]=x;
        find_root(s[i].to);
        mi[x]=max(mi[x],siz[s[i].to]),siz[x]+=siz[s[i].to];
    }
    mi[x]=max(mi[x],N-siz[x]);
    if(mas>mi[x]) mas=mi[x],rot=x;
}
void cz(int x) {
    siz[x]=1;
    for(int i = head[x]; i != 0; i = s[i].next) {
        if(s[i].to==fa[x]) continue;
        if(paint[s[i].to]!=paint[x]) continue;
        fa[s[i].to]=x,cz(s[i].to),siz[x]+=siz[s[i].to];
    }
}
void low(int x) {
    for(int i = head[x]; i != 0; i = s[i].next) {
        if(s[i].to==fa[x]) continue;
        if(paint[s[i].to]!=paint[x]) continue;
        deep[s[i].to]=deep[x]+s[i].val,fa[s[i].to]=x,low(s[i].to),siz[x]+=siz[s[i].to];
    }
    ++dfn,stackk[dfn]=x,paint[x]=color_id;
}
void dfs(int x) {
    int ma[11111111];
    if(N==1) return;
    int yousb[41111],sz[41111],lowbit=0;
    fa[x]=rot=0,mas=1e9,find_root(x);
    fa[rot]=0,cz(rot),deep[rot]=0;
    ma[0]=1;
    for(int i = head[rot]; i != 0; i = s[i].next) {
        if(paint[s[i].to]!=paint[rot]) continue;
        ++lowbit,yousb[lowbit]=s[i].to,sz[lowbit]=siz[s[i].to];
        dfn=0,++color_id,deep[s[i].to]=s[i].val,low(s[i].to);
        for(int j = 1; j <= dfn; j++) for(int kk = 1; kk <= kn; kk++)
                if(k[kk]-deep[stackk[j]]>=0) ans[kk]+=ma[k[kk]-deep[stackk[j]]];
        for(int j = 1; j <= dfn; j++) if(deep[stackk[j]]<=1e7) ma[deep[stackk[j]]]++;
    }
    for(int i = 1; i <= lowbit; i++) N=sz[i],dfs(yousb[i]);
}
void add_edge(int id,int U,int V,int VAL) {
    if(head[U]==0) head[U]=id;
    else s[last[U]].next=id;
    last[U]=id,s[id].to=V,s[id].val=VAL;
}
int main() {
    scanf("%d%d",&n,&kn);
    for(int i = 1; i < n; i++) {
        scanf("%d%d%d",&u,&v,&q);
        add_edge(i*2-1,u,v,q);
        add_edge(i*2,v,u,q);
    }
    for(int i = 1; i <= kn; i++) scanf("%d",&k[i]);
    N=n;
    dfs(1);
    for(int i = 1; i <= kn; i++) printf("%s\n",ans[i]!=0?"AYE":"NAY");
    return 0;
}

map

#include<bits/stdc++.h>
using namespace std;
int kn,N,n,k[23333],u,v,q,siz[41111],rot,mas,fa[41111],mi[41111],paint[41111],deep[41111],color_id;
int head[41111],last[41111],ans[23333],stackk[41111],dfn;
struct node{
    int to,next,val;
} s[233333];
void find_root(int x){
    siz[x]=1,mi[x]=0;
    for(int i = head[x]; i != 0; i = s[i].next){
        if(s[i].to==fa[x]) continue;
        if(paint[s[i].to]!=paint[x]) continue;
        fa[s[i].to]=x;
        find_root(s[i].to);
        mi[x]=max(mi[x],siz[s[i].to]),siz[x]+=siz[s[i].to];
    }
    mi[x]=max(mi[x],N-siz[x]);
    if(mas>mi[x]) mas=mi[x],rot=x;
}
void cz(int x){
    siz[x]=1;
    for(int i = head[x]; i != 0; i = s[i].next){
        if(s[i].to==fa[x]) continue;
        if(paint[s[i].to]!=paint[x]) continue;
        fa[s[i].to]=x,cz(s[i].to),siz[x]+=siz[s[i].to];
    }
}
void low(int x){
    for(int i = head[x]; i != 0; i = s[i].next){
        if(s[i].to==fa[x]) continue;
        if(paint[s[i].to]!=paint[x]) continue;
        deep[s[i].to]=deep[x]+s[i].val,fa[s[i].to]=x,low(s[i].to),siz[x]+=siz[s[i].to];
    }
    ++dfn,stackk[dfn]=x,paint[x]=color_id;
}
void dfs(int x){
    map<int,int> ma;
    if(N==1) return;
    int yousb[41111],sz[41111],lowbit=0;
    fa[x]=rot=0,mas=1e9,find_root(x);
    fa[rot]=0,cz(rot),deep[rot]=0;
    ma[0]=1;
    for(int i = head[rot]; i != 0; i = s[i].next) {
        if(paint[s[i].to]!=paint[rot]) continue;
        ++lowbit,yousb[lowbit]=s[i].to,sz[lowbit]=siz[s[i].to];
        dfn=0,++color_id,deep[s[i].to]=s[i].val,low(s[i].to);
        for(int j = 1; j <= dfn; j++) for(int kk = 1; kk <= kn; kk++) ans[kk]+=ma[k[kk]-deep[stackk[j]]];
        for(int j = 1; j <= dfn; j++) ma[deep[stackk[j]]]++;
    }
    for(int i = 1; i <= lowbit; i++) N=sz[i],dfs(yousb[i]);
}
void add_edge(int id,int U,int V,int VAL){
    if(head[U]==0) head[U]=id;
    else s[last[U]].next=id;
    last[U]=id,s[id].to=V,s[id].val=VAL;
}
int main(){
    scanf("%d%d",&n,&kn);
    for(int i = 1; i < n; i++){
        scanf("%d%d%d",&u,&v,&q);
        add_edge(i*2-1,u,v,q);
        add_edge(i*2,v,u,q);
    }
    for(int i = 1; i <= kn; i++) scanf("%d",&k[i]);
    N=n;
    dfs(1);
    for(int i = 1; i <= kn; i++) printf("%s\n",ans[i]!=0?"AYE":"NAY");
    return 0;
}

求助求助求助求助求助