alpharchmage @ 2024-07-16 09:52:35
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n = 0 , m = 0 , cnt = 0 , root_now = 0 , sum_now = 0 , tot = 0 , tmp = 0;
array<int , 2000100> head , dis , vis , query , sizes , dp , solved , exist , del;
bitset<100000100> judged;
struct Node{
int to;
int val;
int nxt;
};
array<Node , 2000100> edge;
void new_line(int a , int b , int c)
{
edge.at(++ cnt).to = b;
edge.at(cnt).nxt = head.at(a);
edge.at(cnt).val = c;
head.at(a) = cnt;
return;
}
void get_root(int x , int fa)
{
sizes.at(x) = 1;
dp.at(x) = 0;
for(int e = head.at(x);e;e = edge.at(e).nxt)
{
int to = edge.at(e).to;
if(to != fa && !vis.at(to))
{
get_root(to , x);
sizes.at(x) += sizes.at(to);
dp.at(x) = max(dp.at(x) , sizes.at(to));
}
}
dp.at(x) = max(sizes.at(x) , sum_now - sizes.at(x));
if(dp.at(x) < dp.at(root_now))
{
root_now = x;
}
return;
}
void init(int x , int fa)
{
exist.at(++ tmp) = dis.at(x);
for(int e = head.at(x);e;e = edge.at(e).nxt)
{
int to = edge.at(e).to;
if(to != fa && !vis.at(to))
{
dis.at(to) = dis.at(x) + edge.at(e).val;
init(to , x);
}
}
}
void update(int x)
{
tot = 0;
for(int e = head.at(x);e;e = edge.at(e).nxt)
{
int to = edge.at(e).to;
if(vis.at(to))
{
continue;
}
tmp = 0;
dis.at(to) = edge.at(e).val;
init(to , x);
for(int i = tmp;i >= 1;-- i)
{
for(int k = 1;k <= m;++ k)
{
if(query.at(k) >= exist.at(i))
{
solved.at(k) |= judged.test(query.at(k) - exist.at(i));
}
}
}
for(int i = tmp;i >= 1;-- i)
{
del.at(++ tot) = exist.at(i);
judged.set(exist.at(i)) = true;
}
}
for(int i = 1;i <= tot;++ i)
{
judged.reset(del.at(i)) = false;
}
}
void dfs(int x)
{
vis.at(x) = true;
judged.set(0);
update(x);
for(int e = head.at(e);e;e = edge.at(e).nxt)
{
int to = edge.at(e).to;
if(!vis.at(to))
{
root_now = 0;
dp.at(root_now) = INT_MAX;
sum_now = sizes.at(x);
get_root(to , -1);
dfs(root_now);
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for(int i = 1;i <= (n - 1);++ i)
{
int x = 0 , y = 0 , k = 0;
cin >> x >> y >> k;
new_line(x , y , k);
new_line(y , x , k);
}
for(int i = 1;i <= m;++ i)
{
cin >> query.at(i);
}
dp.at(0) = INT_MAX;
sum_now = n;
get_root(1 , 0);
dfs(root_now);
for(int i = 1;i <= m;++ i)
{
if(solved.at(i))
{
cout << "AYE" << endl;
}
else
{
cout << "NAY" << endl;
}
}
return 0;
}
by _Kamisato_Ayaka_ @ 2024-07-16 10:10:48
Alpha!