这卡常的太过分了吧！

传奇英雄 @ 2020-05-18 09:54:09

by FZzzz @ 2020-05-18 19:27:06

@传奇英雄 你哪里改了嘞……不还是有 memset

by 传奇英雄 @ 2020-05-18 19:38:33

@FZzzz 嗯嗯嗯，我改了1个，还有1个。。。我脑残了。。。

by 传奇英雄 @ 2020-05-18 19:40:08

啊啊啊，点分治把我给搞傻了。。。。

by 传奇英雄 @ 2020-05-18 20:05:52

@FZzzz 我醉了，醉了。没有什么卵用

#include <bits/stdc++.h>
using namespace std;
const int g=10005,h=20005;
int n,m,xx,yy,zz,x[h],y[h],z[g],w[h],s,a[g];
int d[g],dp[g],dd[g],u,v,e,m1,fa,sum,big;
int b[g],cnt;
bool f[g],fl[g],f3[10000005];

inline int read()
{
    int F=1,Num=0; //F是记录数字是否为负数，Num存储读入的数字
    char ch=getchar(); //getchar()读取一个字符
    while(!isdigit(ch)) //isdigit()判断是否为数字
    {
        if(ch=='-') F=-1; //如果读入的字符是符号，标记F
        ch=getchar(); //继续读字符
    }
    while(isdigit(ch)) //如果当前读入的字符是数字，则将整个数字全部读入
    {
        Num=Num*10+ch-'0'; //将读入的ASCII字符转换为数字
        //或者上面的代码可以这样写:Num=(Num<<1)+(Num<<3)+ch-'0';
        ch=getchar(); //读取下一个字符
    }
    return Num*F; //将读取完毕的字符返回
}

void get(int xx,int yy)
{
    x[++s]=z[xx];
    y[s]=yy;
    z[xx]=s;
    w[s]=zz;
}

void dfs(int t,int fa)//找重心
{
    dp[t]=1,dd[t]=0;
    for(int i=z[t];i;i=x[i])
        if(y[i]!=fa&&!f[y[i]])
        {
            dfs(y[i],t);
            dp[t]+=dp[y[i]];
            dd[t]=max(dd[t],dd[y[i]]+1);
        }
    m1=max(dd[t],e-dd[t]-1);
    if(m1<u) u=m1,v=t;
}

void dfs2(int t)
{
    m1=max(dd[t],e-dd[t]-1);
    if(m1<u) u=m1,v=t;
    for(int i=z[t];i;i=x[i])
        if(dp[y[i]]<dp[t]&&!f[y[i]])
            dfs2(y[i]);
}

void d2(int t,int fa)
{
    b[++cnt]=d[t];
    for(int i=z[t];i;i=x[i])
        if(y[i]!=fa&&!f[y[i]])
        {
            d[y[i]]=d[t]+w[i];
            if(d[y[i]]<=big) d2(y[i],t);
        }
}

void find(int t)
{
    f[v]=1;
    cnt=1;
    int m2;
    for(int i=z[v];i;i=x[i])
    {
        m2=cnt+1;
        if(!f[y[i]])
        {
            fa=y[i];
            d[y[i]]=w[i];
            d2(y[i],t);
        }
        for(int k=1;k<=m;k++)
            if(!fl[k])
            {
                for(int j=m2;j<=cnt;j++)
                    if(a[k]>=b[j])
                        if(f3[a[k]-b[j]])
                        {
                            fl[k]=1;
                            sum++;
                            if(sum==m)
                            {
                                for(int ac=1;ac<=m;ac++)
                                    printf("AYE\n");
                                exit(0);
                            }
                            break;
                        }
            }
        for(int j=m2;j<=cnt;j++)
            f3[b[j]]=1;
    }
    for(int i=2;i<=cnt;i++)
        f3[b[i]]=0;
    m2=v;
    for(int i=z[m2];i;i=x[i])
        if(!f[y[i]])
        {
            if(dp[y[i]]<dp[m2])
            {
                e=dp[y[i]],u=n;
                dfs2(y[i]);
            }
            else
            {
                e=dp[t]-dp[m2],u=n;
                dfs(y[i],m2);
            }
            find(v);
        }
}

int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    //scanf("%d%d",&n,&m);
    n = read(), m = read();
    for(int i=1;i<n;i++)
    {
        //scanf("%d%d%d",&xx,&yy,&zz);
        xx = read(), yy = read(), zz = read();
        get(xx,yy);
        get(yy,xx);
    }
    for(int i=1;i<=m;i++)
    {
        //scanf("%d",&a[i]);
        a[i] = read();
        big=max(big,a[i]);
    }
    e=u=n;//e为子树总大小
    dfs(1,1);
    f3[0]=1;
    find(1);
    for(int i=1;i<=m;i++)
        if(fl[i]) printf("AYE\n");
        else printf("NAY\n");
    return 0;
}

by 传奇英雄 @ 2020-05-19 10:28:08

改了一下重心。#7是241ms，#9是349ms。。卡爆了

by 传奇英雄 @ 2020-05-19 10:57:01

OK，问题已解决。这个题是我的错，和出题人卡常无关。

by 传奇英雄 @ 2020-05-19 10:57:21

有一个地方字母手残写错了。。