Danno0v0 @ 2022-08-10 12:09:07
卡不过去
#include<bits/stdc++.h>
#define Max 2000001
using namespace std;
int tmp[Max],tmpcnt;
bool judge[Max],vis[Max],ans[Max];
int fi[Max],to[Max],nx[Max],co[Max],edgetot,tot;
int size[Max],maxson[Max],dis[Max],root;
int ask[Max];
int q[Max];
int n,m;
void link(int a,int b,int c)
{
nx[++edgetot]=fi[a];
fi[a]=edgetot;
to[edgetot]=b;
co[edgetot]=c;
}
void getdis(int x,int fa)
{
tmp[++tmpcnt]=dis[x];
for(int i=fi[x];i;i=nx[i])
{
int v=to[i];
if(vis[v]||v==fa) continue;
dis[v]=dis[x]+co[i];
if(dis[v]>1000000) continue;
getdis(v,x);
}
}
void calc(int x)
{
int qcnt;
for(int i=fi[x];i;i=nx[i])
{
int v=to[i];
if(vis[v]) continue;
tmpcnt=0;
dis[v]=co[i];
getdis(v,x);
for(int k=1;k<=tmpcnt;k++)
for(int l=1;l<=m;l++)
if(tmp[k]<=ask[l])
ans[l]|=judge[ask[l]-tmp[k]];
for(int k=1;k<=tmpcnt;k++)
q[++qcnt]=tmp[k],judge[tmp[k]]=1;
}
for(int i=1;i<=qcnt;i++)
judge[q[i]]=0;
}
void getsize(int x,int fa)
{
size[x]=1;
maxson[x]=0;
for(int i=fi[x];i;i=nx[i])
{
int v=to[i];
if(vis[x]||v==fa) continue;
getsize(v,x);
size[x]+=size[v];
maxson[x]=max(maxson[x],size[v]);
}
maxson[x]=max(maxson[x],tot-maxson[x]);
if(maxson[x]<maxson[root]) root=x;
}
void solve(int x)
{
vis[x]=judge[0]=1;
calc(x);
for(int i=fi[x];i;i=nx[i])
{
int v=to[i];
if(vis[v]) continue;
tot=size[v];
maxson[root=0]=Max;
getsize(v,0);
solve(root);
}
}
int main()
{
ios::sync_with_stdio(false);
int a,b,c;
cin>>n>>m;
for(int i=1;i<n;i++)
{
cin>>a>>b>>c;
link(a,b,c);
link(b,a,c);
}
for(int i=1;i<=m;i++)
cin>>ask[i];
maxson[root=0]=Max;
tot=n;
getsize(1,0);
solve(root);
for(int i=1;i<=m;i++)
{
if(ans[i]) cout<<"AYE"<<'\n';
else cout<<"NAY"<<'\n';
}
}
by Danno0v0 @ 2022-08-10 14:21:11
哦
原来是我写挂了