此题数据急需加强

RT

//这是90分代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005;
inline int read()
{
    int res=0,f=1;char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
        res=res*10+c-48,c=getchar();
    return res*f;
}
int n,m,qur[1005],siz[N],maxx[N],rt,dis[N];
int head[N],to[N<<1],nxt[N<<1],val[N<<1],cnt;
bool vis[1005],sgl[N];
inline void add(int x,int y,int v)
{
    ++cnt;
    nxt[cnt]=head[x];
    head[x]=cnt;
    val[cnt]=v;
    to[cnt]=y;
    return;
}
void find_root(int x,int fa,int tot)
{
    siz[x]=1;maxx[x]=0;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[x];
        if(y!=fa&&!sgl[y])
        {
            find_root(y,x,tot);
            siz[x]+=siz[y];
            maxx[x]=max(maxx[x],siz[y]);
        }
    }
    maxx[x]=max(maxx[x],tot-siz[x]);
    if(maxx[x]<maxx[rt]) rt=x;
    return;
}
int tp,a[N],ff[N];
inline bool cmp(int x,int y){return dis[x]<dis[y];}
void dfs(int x,int fa,int len,int gen)
{
    dis[x]=len;ff[x]=gen;a[++tp]=x;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(!sgl[y]&&y!=fa)
        {
            dfs(y,x,len+val[i],gen);
        }
    }
    return;
}
void calc(int x)
{
    tp=0;a[++tp]=x;dis[x]=0;ff[x]=x;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(!sgl[y])
        {
            dfs(y,x,val[i],y);
        }
    }
    sort(a+1,a+tp+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(!vis[i])
        {
            int l=1,r=tp;
            while(l<tp&&dis[a[l]]+dis[a[r]]<qur[i]) l++;
            while(l<r)
            {
                if(dis[a[l]]+dis[a[r]]>qur[i]) r--;
                else if(dis[a[l]]+dis[a[r]]<qur[i]) l++;
                else if(ff[a[l]]==ff[a[r]])
                {
                    if(dis[a[r]]==dis[a[r-1]]) r--;
                    else l++;
                }
                else
                {
                    vis[i]=1;
                    break;
                }
            }
        }
    }
    return;
}
void solve(int x)
{
    if(x==0) return;
    sgl[x]=1;
    calc(x);
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(!sgl[y])
        {
            rt=0;
            find_root(y,x,siz[y]);
            solve(rt);
        }
    }
    return;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n-1;i++)
    {
        int x=read(),y=read(),v=read();
        add(x,y,v),add(y,x,v);
    }
    for(int i=1;i<=m;i++) qur[i]=read();
    maxx[0]=N;
    find_root(1,0,n);
    solve(rt);
    for(int i=1;i<=m;i++)
    {
        if(vis[i]) puts("AYE");
        else puts("NAY");
    }
    return 0;
}

100分只需将

void find_root(int x,int fa,int tot)
{
    siz[x]=1;maxx[x]=0;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[x];
        if(y!=fa&&!sgl[y])
        {
            find_root(y,x,tot);
            siz[x]+=siz[y];
            maxx[x]=max(maxx[x],siz[y]);
        }
    }
    maxx[x]=max(maxx[x],tot-siz[x]);
    if(maxx[x]<maxx[rt]) rt=x;
    return;
}

改成

void find_root(int x,int fa,int tot)
{
    siz[x]=1;maxx[x]=0;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(y!=fa&&!sgl[y])
        {
            find_root(y,x,tot);
            siz[x]+=siz[y];
            maxx[x]=max(maxx[x],siz[y]);
        }
    }
    maxx[x]=max(maxx[x],tot-siz[x]);
    if(maxx[x]<maxx[rt]) rt=x;
    return;
}

令人难以置信上面的错误代码竟然有分？？