求大佬改错

P3806 【模板】点分治 1

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;
}

|