萌新求调点分治

Jorisy @ 2024-03-30 20:09:56

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>>g[10005];
int n,m,wc,sz[10005],d[10005],f[10005],nowd[10005],sum,q[10000005],ans[10005],vis[10005],jd[10000005];

void dfswc(int p,int lst)
{
    //cerr<<'w';
    sz[p]=1;
    f[p]=0;
    for(auto i:g[p])
    {
        if(i.first==lst||vis[i.first]) continue;
        dfswc(i.first,p);
        sz[p]+=sz[i.first];
        f[p]=max(f[p],sz[i.first]);
    }
    f[p]=max(f[p],n-sz[p]);
    if(f[p]<f[wc]) wc=p;
}

void dfsd(int p,int lst)
{
    //cerr<<'d';
    nowd[++nowd[0]]=d[p];
    for(auto i:g[p])
    {
        if(i.first==lst||vis[i.first]) continue;
        d[i.first]=d[p]+i.second;
        dfsd(i.first,p);
    }
}

void vdiv(int p)
{
    //cerr<<'v'<<p<<endl;
    vis[p]=jd[0]=1;
    int t=0;
    for(auto i:g[p])
    {
        if(vis[i.first]) continue;
        nowd[0]=0;
        d[i.first]=i.second;
        dfsd(i.first,p);
        for(int j=nowd[0];j;j--)
        {
            for(int k=1;k<=m;k++)
            {
                if(q[k]>=nowd[j]) ans[k]|=jd[q[k]-nowd[j]];
            }
        }
        for(int j=nowd[0];j;j--)
        {
            q[++t]=nowd[j];
            jd[nowd[j]]=1;
        }
    }
    for(int i=1;i<=t;i++) jd[q[i]]=0; 
    //cerr<<'|';
    for(auto i:g[p])
    {
        if(vis[i.first]) continue;
        sum=sz[i.first];
        f[wc=0]=1e9;
        dfswc(i.first,0);
        vdiv(wc);
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(int i=1;i<=m;i++) cin>>q[i];
    f[wc]=sum=n;
    dfswc(1,0);
    vdiv(wc);
    for(int i=1;i<=m;i++) puts(ans[i]?"AYE":"NAY");
    return 0;
}

by Super_Cube @ 2024-03-30 21:25:05

@Shiota_Kaede 点分治里的垃圾桶和一开始的询问重名了，都是 q 数组。

by Super_Cube @ 2024-03-30 21:28:56

@Shiota_Kaede 帮你改对了，除了前面提到的还有些其他错误，对比一下代码吧。

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>>g[10005];
int n,m,wc,sz[10005],d[10005],f[10005],nowd[10005],sum,q[10005],ans[10005],vis[10005],jd[10000005],th[10005];

void dfswc(int p,int lst)
{
    //cerr<<'w';
    sz[p]=1;
    f[p]=0;
    for(auto i:g[p])
    {
        if(i.first==lst||vis[i.first]) continue;
        dfswc(i.first,p);
        sz[p]+=sz[i.first];
        f[p]=max(f[p],sz[i.first]);
    }
    f[p]=max(f[p],sum-sz[p]);
    if(f[p]<f[wc]) wc=p;
}

void dfsd(int p,int lst)
{
    if(d[p]>10000000)return;
    //cerr<<'d';
    nowd[++nowd[0]]=d[p];
    for(auto i:g[p])
    {
        if(i.first==lst||vis[i.first]) continue;
        d[i.first]=d[p]+i.second;
        dfsd(i.first,p);
    }
}

void vdiv(int p)
{
    //cerr<<'v'<<p<<endl;
    jd[0]=1;
    int t=0;
    th[++t]=0;
    for(auto i:g[p])
    {
        if(vis[i.first]) continue;
        nowd[0]=0;
        d[i.first]=i.second;
        dfsd(i.first,p);
        for(int j=nowd[0];j;j--)
        {
            for(int k=1;k<=m;k++)
            {
                if(q[k]>=nowd[j]) ans[k]|=jd[q[k]-nowd[j]];
            }
        }
        for(int j=nowd[0];j;j--)
        {
            th[++t]=nowd[j];
            jd[nowd[j]]=1;
        }
    }
    for(int i=1;i<=t;i++) jd[th[i]]=0;
    //cerr<<'|';
    vis[p]=1;
    dfswc(p,0);
    for(auto i:g[p])
    {
        if(vis[i.first]) continue;
        sum=sz[i.first];
        f[wc=0]=1e9;
        dfswc(i.first,0);
        vdiv(wc);
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(int i=1;i<=m;i++) cin>>q[i];
    f[0]=sum=n;
    dfswc(1,0);
    vdiv(wc);
    for(int i=1;i<=m;i++) puts(ans[i]?"AYE":"NAY");
    return 0;
}

by Jorisy @ 2024-03-31 06:30:35

@Super_Cube 感谢大佬！！/bx