```cpp
#include<bits/stdc++.h>
using namespace std;
struct apple
{
int dep,sy;
bool operator<(const apple &other)const
{
return sy<other.sy;
}
}e[10005];
int K,tot,q[10005],sy[10005],vist[10005],sz[10005],dep[10005];
int mp[10000005];
vector<pair<int,int> >g[10005];
void dfs(int x,int la)
{
q[++tot]=x;
sz[x]=1;
for(int i=0;i<g[x].size();i++)
{
int cu=g[x][i].first,c2=g[x][i].second;
if(cu==la||vist[cu])continue;
dfs(cu,x);
sz[x]+=sz[cu];
}
}
void dfss(int x,int la,int l)
{
sy[x]=l;
for(int i=0;i<g[x].size();i++)
{
int cu=g[x][i].first,c2=g[x][i].second;
if(cu==la||vist[cu])continue;
dep[cu]=dep[x]+c2;
dfss(cu,x,l);
}
}
int merg(int x)
{
tot=0;
dfs(x,0);
if(sz[x]==1)
{
vist[x]=1;
return 0;
}
int aaa=INT_MAX,w;
for(int i=1;i<=tot;i++)
{
int mx=sz[x]-sz[q[i]];
for(int j=0;j<g[q[i]].size();j++)
{
int cu=g[q[i]][j].first,c2=g[q[i]][j].second;
if(vist[cu]||sz[cu]>sz[q[i]])continue;
mx=max(mx,sz[cu]);
}
if(aaa>mx)aaa=mx,w=q[i];
}
vist[w]=1,sy[w]=-1,dep[w]=0;
for(int i=0;i<g[w].size();i++)
{
int cu=g[w][i].first,c2=g[w][i].second;
if(vist[cu])continue;
dep[cu]=c2;
dfss(cu,w,i);
}
for(int i=1;i<=tot;i++)e[i].sy=sy[q[i]],e[i].dep=dep[q[i]];
sort(e+1,e+tot+1);
int ans=0;
for(int i=1;i<=tot;)
{
int wz=i;
while(wz<tot&&e[wz+1].sy==e[wz].sy)wz++;
for(int j=i;j<=wz;j++)if(e[j].dep<=K)ans+=mp[e[j].dep];
for(int j=i;j<=wz;j++)if(K>=e[j].dep)mp[K-e[j].dep]++;
i=wz+1;
}
for(int i=1;i<=tot;i++)if(K>=e[i].dep)mp[K-e[i].dep]=0;
if(ans)return 1;
for(int i=0;i<g[w].size();i++)
{
int cu=g[w][i].first;
if(vist[cu])continue;
ans+=merg(cu);
if(ans)return 1;
}
return ans;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].push_back(make_pair(v,w));
g[v].push_back(make_pair(u,w));
}
while(m--)
{
scanf("%d",&K);
for(int i=1;i<=n;i++)vist[i]=0;
if(merg(1))printf("AYE\n");
else printf("NAY\n");
}
return 0;
}
```
by lqyc @ 2021-07-22 20:12:01
确实不卡常，应该是你假了
by cyffff @ 2021-07-22 20:40:21