求助,现在桶做法是被卡了吗

P3806 【模板】点分治 1

Danno0v0 @ 2022-08-10 12:09:07

卡不过去

#include<bits/stdc++.h>
#define Max 2000001
using namespace std;
int tmp[Max],tmpcnt;
bool judge[Max],vis[Max],ans[Max];
int fi[Max],to[Max],nx[Max],co[Max],edgetot,tot;
int size[Max],maxson[Max],dis[Max],root;
int ask[Max];
int q[Max];
int n,m;
void link(int a,int b,int c)
{
    nx[++edgetot]=fi[a];
    fi[a]=edgetot;
    to[edgetot]=b;
    co[edgetot]=c;
}
void getdis(int x,int fa)
{
    tmp[++tmpcnt]=dis[x];
    for(int i=fi[x];i;i=nx[i])
    {
        int v=to[i];
        if(vis[v]||v==fa) continue;
        dis[v]=dis[x]+co[i];
        if(dis[v]>1000000) continue;
        getdis(v,x);
    }
}
void calc(int x)
{
    int qcnt;
    for(int i=fi[x];i;i=nx[i])
    {
        int v=to[i];
        if(vis[v]) continue;
        tmpcnt=0;
        dis[v]=co[i];
        getdis(v,x);
        for(int k=1;k<=tmpcnt;k++)
            for(int l=1;l<=m;l++)
                if(tmp[k]<=ask[l])
                    ans[l]|=judge[ask[l]-tmp[k]];
        for(int k=1;k<=tmpcnt;k++)
            q[++qcnt]=tmp[k],judge[tmp[k]]=1;
    }
    for(int i=1;i<=qcnt;i++)
        judge[q[i]]=0;
}
void getsize(int x,int fa)
{
    size[x]=1;
    maxson[x]=0;
    for(int i=fi[x];i;i=nx[i])
    {
        int v=to[i];
        if(vis[x]||v==fa) continue;
        getsize(v,x);
        size[x]+=size[v];
        maxson[x]=max(maxson[x],size[v]);
    }
    maxson[x]=max(maxson[x],tot-maxson[x]);
    if(maxson[x]<maxson[root]) root=x;
}
void solve(int x)
{
    vis[x]=judge[0]=1;
    calc(x);
    for(int i=fi[x];i;i=nx[i])
    {
        int v=to[i];
        if(vis[v]) continue;
        tot=size[v];
        maxson[root=0]=Max;
        getsize(v,0);
        solve(root);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int a,b,c;
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b>>c;
        link(a,b,c);
        link(b,a,c);
    }
    for(int i=1;i<=m;i++)
        cin>>ask[i];
    maxson[root=0]=Max;
    tot=n;
    getsize(1,0);
    solve(root);
    for(int i=1;i<=m;i++)
    {
        if(ans[i]) cout<<"AYE"<<'\n';
        else cout<<"NAY"<<'\n';
    }
}

by Danno0v0 @ 2022-08-10 14:21:11

原来是我写挂了


|