为什么TLE10个点啊...第一个点我在本机只跑了0.03s啊...

ｃｈｉｌｌ @ 2018-07-07 15:21:57

by ｃｈｉｌｌ @ 2018-07-07 15:23:08

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#define REP(i,x,y) for (int i=x;i<=y;i++)
#define EDG(i,x) for (int i=h[x];i;i=e[i].next)
#define INF 0x7fffffff
using namespace std;

const int N=10005;
int n,q,cnt,sum,ans,ask,root,deep;
int h[N],dep[N],d[N],f[N],son[N],vis[N];
struct EDGE{int next,to,val;}e[N<<1];
map <int,int> _;

void ADD(int u,int v,int w){
    e[++cnt]=(EDGE){h[u],v,w};
    h[u]=cnt;
}

void ROOT(int u,int fa){
    son[u]=1;f[u]=0;
    EDG(i,u){
        int v=e[i].to;
        if (v==fa||vis[v]) continue;
        ROOT(v,u);
        son[u]+=son[v];
        f[u]=max(f[u],son[v]);
    }
    f[u]=max(f[u],sum-son[u]);
    if (f[u]<f[root]) root=u;
}

void DEEP(int u,int fa){
    dep[++deep]=d[u];
    EDG(i,u){
        int v=e[i].to;
        if (v==fa||vis[v]) continue;
        d[v]=d[u]+e[i].val; 
        DEEP(v,u);
    }
}

void CALC(int u,int fuck,int shit){
    d[u]=fuck;deep=0;
    DEEP(u,0);
    int l,r,res=0;
    REP(i,1,deep-1) REP(j,i+1,deep) _[dep[i]+dep[j]]+=shit; 
}

void WORK(int u){
    CALC(u,0,1);vis[u]=1;
    EDG(i,u){
        int v=e[i].to;
        if (vis[v]) continue;
        CALC(v,e[i].val,-1);
        sum=son[v];root=0;
        ROOT(v,root);WORK(root);
    }
}

int READ(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') if (ch=='-') f=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int main(){
    n=READ();q=READ();
    REP(i,1,n-1){
        int u=READ(),v=READ(),w=READ();
        ADD(u,v,w);ADD(v,u,w);
    }
    sum=n;f[0]=INF;
    ROOT(1,0);WORK(root);
    REP(i,1,q){
        ask=READ();
        if (_[ask]) printf("AYE\n"); else printf("NAY\n");
    }
    return 0;
}

by ｃｈｉｌｌ @ 2018-07-07 20:02:40

去掉快读就AC，真的佛了

by Prurite @ 2018-07-25 15:40:37

@病名為愛 您的快读是错的啊

by Prurite @ 2018-07-25 15:41:25

while (ch<'0'||ch>'9') if (ch=='-') f=-1,ch=getchar();

一句很显然应改为

while (ch<'0'||ch>'9')
    if (ch=='-') f=-1;
    ch=getchar();

by Prurite @ 2018-07-25 15:41:57

(当然要打上大括号)