萌新刚学OI，求助！！！

bellmanford @ 2020-03-15 17:53:08

void find_root(int u,int fa){
    size[u]=1;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||vis[v]) continue;
        find_root(v,u);
        size[u]+=size[v];
    }
    if(maxn>max(size[u],sum-size[u]))
        maxn=max(size[u],sum-size[u]),root=u;
}

void dfs(int u){
    calc(u,0,1);vis[u]=1;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].val;
        if(vis[v]) continue;
        calc(v,w,-1);sum=size[u],maxn=1e9;
        find_root(v,u);dfs(root);
    }
}

by ZhangJiahao0918 @ 2020-03-15 17:54:18

QNDGXOI

by bellmanford @ 2020-03-15 17:55:46

by ZhangJiahao0918 @ 2020-03-15 17:57:40

@bellmanford

我表示看不懂

%%%%%

by function_of_zero @ 2020-03-15 17:58:07

@bellmanford 我记得uoj上有篇博客说有两种找重心的方法都是对的？而且这题数据水

by mot1ve @ 2020-03-15 17:58:49

刚学OI就蓝勾，太fake了

by bellmanford @ 2020-03-15 18:00:14

@zzzZF 这题数据水。。。

by function_of_zero @ 2020-03-15 18:01:53

@bellmanford 啊，我记得以前是可以用各种方法水过去的，加强一次之后就不知道怎么样了

by dingcx @ 2020-03-15 18:03:05

qndmxgxOI 根本看不懂好吧

by bellmanford @ 2020-03-15 18:04:36

@zzzZF IEE

管理员说了能卡掉所有找错重心的方法，所以这是错误的还是正确的鸭？？？

完整代码：

#include<iostream>
#include<cstdio>
using namespace std;

#define max(x,y) (x>y?x:y)
const int M=1e5+5,N=1e7+5;

int n,m,tot=0,cnt=0,sum=0,root=0,maxn=0;
int cc[M],ans[M],dis[M],size[M],query[M],first[M];
bool vis[M],book[N];
struct Edge{
    int nxt,to,val;
}e[M<<1];

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

void add(int x,int y,int z){
    e[++tot].nxt=first[x];
    first[x]=tot;
    e[tot].to=y;
    e[tot].val=z;
}

void dfs2(int u,int fa){
    cc[++cnt]=u;size[u]=1;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].val;
        if(v==fa||vis[v]) continue;
        dis[v]=dis[u]+w;
        dfs2(v,u);
        size[u]+=size[v];
    }
}

void calc(int u,int w,int c){
    cnt=0,dis[u]=w;dfs2(u,0);
    for(int i=1;i<=cnt;i++) if(dis[cc[i]]<N) book[dis[cc[i]]]=1;
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=m;j++)
            if(dis[cc[i]]<=query[j])
                if(book[query[j]-dis[cc[i]]])
                    ans[j]+=c;
    for(int i=1;i<=cnt;i++) if(dis[cc[i]]<N) book[dis[cc[i]]]=0;
}

void find_root(int u,int fa){
    size[u]=1;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||vis[v]) continue;
        find_root(v,u);
        size[u]+=size[v];
    }
    if(maxn>max(size[u],sum-size[u]))
        maxn=max(size[u],sum-size[u]),root=u;
}

void dfs(int u){
    calc(u,0,1);vis[u]=1;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].val;
        if(vis[v]) continue;
        calc(v,w,-1);sum=size[u],maxn=1e9;
        find_root(v,u);dfs(root);
    }
}

int main(){
//  freopen("P3806_8.in","r",stdin);
//  freopen("ans.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n-1;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    for(int i=1;i<=m;i++) query[i]=read(),ans[i]=0;
    sum=n,maxn=1e9;find_root(1,0),dfs(root);
    for(int i=1;i<=m;i++) printf("%s\n",ans[i]>0?"AYE":"NAY");
}

by bellmanford @ 2020-03-15 18:05:37

但是这个要开O2才能跑过谔谔