求助淀粉质,不知道哪里写挂了,wa4 6

P3806 【模板】点分治 1

Zkl21 @ 2023-06-09 10:12:05

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10,M=N<<1,S=1e7+10;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
bool st[N];
int q[N],p[N],k[110];
bool f[S],ans[110];
void add(int a,int b,int c)
{//加边
    e[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int get_size(int u,int fa)
{//得到子树大小
    if(st[u])return 0;
    int res=1;
    for(int i=h[u],j=e[i];i;i=ne[i],j=e[i])
        if(j!=fa)res+=get_size(j,u);
    return res;
}
int get_wc(int u,int fa,int tot,int &wc)
{//求子树的重心,tot是整棵树的大小,求得的重心存到wc中
    if(st[u])return 0;
    int sum=1,ms=0;//sum记录子树大小,ms记录最大的子树的大小
    for(int i=h[u],j=e[i];i;i=ne[i],j=e[i])
        if(j!=fa)
        {
            int t=get_wc(j,u,tot,wc);
            ms=max(ms,t);
            sum+=t;
        }
    ms=max(ms,tot-sum);
    if(ms<=tot/2)wc=u;
    return sum;
}
void get_dist(int u,int fa,int dist,int &qt)
{//更新子树每一节点到重心u的距离,存到q中
    if(st[u])return;
    q[qt++]=dist;
    for(int i=h[u],j=e[i];i;i=ne[i],j=e[i])
        if(j!=fa)get_dist(j,u,dist+w[i],qt);
}
void calc(int u)
{
    if(st[u])return;
    get_wc(u,-1,get_size(u,-1),u);//找重心
    st[u]=1;//标记该节点,表示删除该节点
    int pt=0;//p数组大小
    f[0]=1;//不知道啥用
    for(int i=h[u],j=e[i];i;i=ne[i],j=e[i])
    {
        int qt=0;//q数组大小
        get_dist(j,u,w[i],qt);//求子树结点到u的距离
        for(int l=0;l<qt;l++)
        {
            auto t=q[l];//取出每一个点到重心的距离
            if(t>1e7)continue;//大于1e7跳过
            p[pt++]=t;//将小于等于1e7的部分放入p数组中
            f[t]=1;//标记存在距离为t的两个结点
        }
    }
    for(int i=1;i<=m;i++)
        if(!ans[i])//每次的输入是否已经确定答案
        {
            if(f[k[i]])
            {//存在这个情况
                ans[i]=1;//标记
                continue;
            }
            for(int j=0;j<pt;j++)
                if(k[i]>=p[j]&&f[k[i]-p[j]])
                {//对于每一个答案,查一下有没有两个结点的距离
                    ans[i]=1;//标记
                    break;
                }
        }
    for(int i=0;i<pt;i++)
        if(p[i]<=1e7)f[p[i]]=0;//清空桶
    for(int i=h[u],j=e[i];i;i=ne[i],j=e[i])calc(j);
}
int main()
{
    #ifdef Luogu
        freopen("E:\\in and out\\in.in","r",stdin);
        freopen("E:\\in and out\\out.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    for(int i=1;i<=m;i++)cin>>k[i];
    calc(1);
    for(int i=1;i<=m;i++)puts(ans[i]?"AYE":"NAY");
    return 0;
}

|