star_magic_young @ 2018-02-22 16:20:56
第四个点WA了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>
#define il inline
#define sta static
#define re register
#define LL long long
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define swap(a,b) a^=b^=a^=b
const int mod=19650827,_=10010,ee=10000010;
using namespace std;
il bool issz(char ch){return ch>='0'&&ch<='9';}
il int rd()
{
char ch;int x=0,w=1;
while(!issz(ch)){if(ch=='-') w=-1;ch=getchar();}
while(issz(ch)){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
return x*w;
}
int to[_<<1],w[_<<1],nt[_<<1],hd[_],tot=1;
int b[ee];
int te[_],tt;
il void add(int x,int y,int z)
{
tot++;to[tot]=y;w[tot]=z;nt[tot]=hd[x];hd[x]=tot;
tot++;to[tot]=x;w[tot]=z;nt[tot]=hd[y];hd[y]=tot;
}
int n,m,rt;
LL ans,hkwdl;
int sz[_],size,dis[_];
bool del[_];
il void zx(int x,int fa)
{
sz[x]=1;
for(int j=hd[x];j;j=nt[j])
if(!del[to[j]]&&fa!=to[j])
{
zx(to[j],x);
sz[x]+=sz[to[j]];
}
if(sz[x]*2>=size&&!rt&&!del[x]) rt=x;
}
il void dfs(int x,int fa)
{
te[++tt]=dis[x];
for(int j=hd[x];j;j=nt[j])
if(!del[to[j]]&&fa!=to[j])
{
dis[to[j]]=dis[x]+w[j];
dfs(to[j],x);
}
}
il void cnt(int ro,int xx,int jj)
{
dis[ro]=xx;
memset(te,0,tt+5);
tt=0;
dfs(ro,0);
/*if(te[0]) tt++;
if(tt==1&&jj==-1) return;*/
for(int i=1;i<=tt;i++)
for(int j=1;j<=tt;j++)
if(te[i]+te[j]<=ee) b[te[i]+te[j]]+=jj;
}
il void work(int ro)
{
sz[ro]=0;rt=0;zx(ro,0);
del[rt]=true;
cnt(rt,0,1);
for(int j=hd[rt];j;j=nt[j])
if(!del[to[j]])
{
cnt(to[j],w[j],-1);
size=sz[to[j]];
work(to[j]);
}
}
il LL gcdd(LL a,LL b)
{
return b==0?a:gcdd(b,a%b);
}
int main()
{
freopen("2.in","r",stdin);
freopen("2.out","w",stdout);
size=n=rd();
m=rd();
int x,y,z;
for(int i=1;i<n;i++)
{
x=rd();y=rd();z=rd();
add(x,y,z);
}
work(1);
b[0]++;
while(m--)
{
x=rd();
b[x]?printf("AYE\n"):printf("NAY\n");
}
return 0;
}