40pts求助bbwb

P3806 【模板】点分治 1

陈刀仔 @ 2019-05-12 22:10:54

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=100050,maxm=150,inf=10000050;
int n,m;
int cnt,head[maxn],next[maxn<<1],to[maxn<<1],w[maxn<<1];
int query[maxm];
int maxp[maxn],dis[maxn],size[maxn],rec[maxn],a[maxn];
bool ok[maxm],bj[inf],banned[maxn];
int all,rt;
void add(int x,int y,int z)
{
    cnt++;
    to[cnt]=y;
    w[cnt]=z;
    next[cnt]=head[x];
    head[x]=cnt;
}
void getroot(int u,int fa)
{
    size[u]=1;maxp[u]=0;
    for(int i=head[u];i;i=next[i])
    {
        int v=to[i];
        if(v!=fa&&!banned[v])
        {
            getroot(v,u);
            size[u]+=size[v];
            maxp[u]=max(maxp[u],size[v]);
        }
    }
    maxp[u]=max(maxp[u],all-size[u]);
    if(maxp[u]<maxp[rt])
        rt=u;
}
void getdis(int u,int fa)
{
    rec[++rec[0]]=dis[u];
    for(int i=head[u];i;i=next[i])
    {
        int v=to[i];
        if(v!=fa&&!banned[v])
        {
            dis[v]=dis[u]+w[i];
            getdis(v,u);
        }
    }
}
void deal(int u)
{
    for(int i=head[u];i;i=next[i])
    {
        int v=to[i];
        if(banned[v])
            continue;
        rec[0]=0;
        dis[v]=dis[u]+w[i];
        getdis(v,u);
        for(int j=1;j<=rec[0];j++)
            for(int k=1;k<=m;k++)
            {
                if(query[k]>=rec[j]&&bj[query[k]-rec[j]]==1)
                    ok[k]=1;
            }
        for(int j=1;j<=rec[0];j++)
        {
            a[++a[0]]=rec[j];
            bj[rec[j]]=1;
        }
    }
    for(int i=1;i<=a[0];i++)
        bj[a[i]]=0;
    a[0]=0;
}
void solve(int u)
{
    bj[0]=1;
    banned[u]=1;
    deal(u);
    for(int i=head[u];i;i=next[i])
    {
        int v=to[i];
        if(!banned[v])
        {
            all=size[v];
            maxp[v]=inf;
            getroot(v,0);
            solve(rt);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=m;i++)
        scanf("%d",&query[i]);
    maxp[rt]=inf;
    all=n;
    getroot(1,0);
    solve(rt);
    for(int i=1;i<=m;i++)
        if(ok[i]==1)
            printf("AYE\n");
        else
            printf("NAY\n");
    return 0;
}

|