1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include<bits/stdc++.h>
using namespace std;
const int maxn=10010,bign=10001000;
int n,m,tmp[bign],judge[bign];
int sz[maxn],vis[maxn];
int head[maxn],qt[maxn];
int size,maxp[maxn];
int tot,rt,dis[maxn];
int q[bign],ynn[maxn];
struct edge{
int next,to,dis;
}e[maxn*2];
inline void addedge(int next,int to,int dis)
{
e[++size].to=to;
e[size].dis=dis;
e[size].next=head[next];
head[next]=size;
}
inline void find(int t,int fat)
{
int i,j;
sz[t]=1;
maxp[t]=0;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(j==fat||vis[j]) continue;
find(j,t);
sz[t]+=sz[j];
maxp[t]=max(sz[j],maxp[t]);
}
maxp[t]=max(maxp[t],tot-sz[t]);
if(maxp[t]<maxp[rt]) rt=t;
}
inline void getdis(int t,int fat)
{
tmp[++tmp[0]]=dis[t];
int i,j,k;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].dis;
if(vis[j]||j==fat) continue;
dis[j]=dis[t]+k;
getdis(j,t);
}
}
inline void cc(int t)
{
int p=0,i,j,k,l;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].dis;
if(vis[j]) continue;
tmp[0]=0;
dis[j]=k;
getdis(j,t);
for(k=tmp[0];k;k--)
for(l=1;l<=m;l++) if(qt[l]>=tmp[k]) ynn[l]|=judge[qt[l]-tmp[k]];
for(k=tmp[0];k;k--) q[++p]=tmp[k],judge[tmp[k]]=1;
}
for(i=p;i;i--) judge[q[i]]=0;
}
inline void divid(int t)
{
int i,j;
vis[t]=judge[0]=1; cc(t);
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(vis[j]) continue;
tot=sz[j];
maxp[rt=0]=bign;
find(j,0);
divid(rt);
}
}
int main()
{
ios::sync_with_stdio(false);
register int i,h;
int t1,t2,t3;
cin>>n>>m;
for(i=1;i<n;i++)
{
cin>>t1>>t2>>t3;
addedge(t1,t2,t3);
addedge(t2,t1,t3);
}
for(i=1;i<=m;i++) cin>>qt[i];
maxp[rt=0]=n;
tot=n;
find(1,0);
divid(rt);
for(i=1;i<=m;i++)
{
if(ynn[i]) cout<<"AYE"<<endl;
else cout<<"NAY"<<endl;
}
return 0;
}
|
