求助,多跑了但是找不到哪多跑了

P3806 【模板】点分治 1

a_sad_soul @ 2023-03-19 17:30:34

点分治多分了但是找不到为什么多分(

#include<bits/stdc++.h>
#define MAXN 100005
#define MAXXN 500000005
using namespace std;
struct node {
    int to,val;
    node *next;
}*tmp,*head[MAXN];
int del[MAXN],n,m,query[MAXN],size[MAXN],dist[MAXN],dis[MAXN];
int root,tot;
bool vis[MAXN],judge[MAXXN],ans[MAXN],S;
void add(int u,int v,int w)
{
    tmp=new node;
    tmp->to=v;
    tmp->val=w;
    tmp->next=head[u];
    head[u]=tmp;
}
int mx[MAXN];
int to1,to2,to3;
void getroot(int u,int fa)
{++to1;
    size[u]=1;
    mx[u]=0;
    for(node *i=head[u];i!=NULL;i=i->next)
    {
        int v=i->to,val=i->val;
        if(v==fa||vis[v])continue;
        getroot(v,u);
        size[u]+=size[v];
       mx[u]=max(size[v],mx[u]);
    }
    mx[u]=max(mx[u],S-size[u]);
    if(mx[u]<size[root])
        root=u;
}
void getdis(int u,int fa)
{++to2;
    dis[++dis[0]]=dist[u];
    for(node *i=head[u];i!=NULL;i=i->next)
    {
        int v=i->to;
        if(v==fa||vis[v])continue;
        dist[v]=dist[u]+i->val; 
        getdis(v,u);
    }
}
void solve(int u)
{
    del[0]=0;
    for(node *i=head[u];i!=NULL;i=i->next)
    {
        int v=i->to;
        //cout<<v<<" "<<vis[v]<<endl;
        if(vis[v])continue;
        dis[0]=0;
        dist[v]=i->val;
        getdis(v,u);
        //cout<<dis[0]<<endl;
        for(int j=1;j<=dis[0];++j)
        {
            for(int k=1;k<=m;++k)
            {
                if(dis[j]<=query[k])
                    ans[k]|=judge[query[k]-dis[j]];

            }//cout<<dis[j]<<endl; 
        }
        for(int j=1;j<=dis[0];++j)judge[dis[j]]=1,del[++del[0]]=dis[j];
        //for(int i=1;j<=dis[0];++)
    }   
    for(int i=1;i<=del[0];++i)
    {
        judge[del[i]]=0;
    }

}
void divide(int u)
{++to3;
    vis[u]=1;
    //cout<<"k"<<endl;
    judge[0]=1;
    solve(u);
    for(node *i=head[u];i!=NULL;i=i->next)
    {
        int v=i->to;
        if(vis[v])continue;
        S=size[v];
        mx[0]=n;
        root=0;
        getroot(v,0);
        divide(root);
    }
}
int main()
{
    //judge[0]=1;
    freopen("1.in","r",stdin);
    freopen("out.txt","w",stdout);
    size[0]=1451041910;
    cin>>n>>m;
    for(int i=1;i<n;++i)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    for(int i=1;i<=m;++i)
        scanf("%d",&query[i]);
    S=n;
    mx[0]=n;
    root=0;
    getroot(1,0);
    //for(int i=1;i<=n;++i)cout<<vis[i];
    //cout<<endl;
    divide(root);
    for(int i=1;i<=m;++i)
        if(ans[i])printf("AYE\n");
        else printf("NAY\n");
    cout<<to1<<endl<<to2<<endl<<to3;
    return 0; 
}

by zjy2008 @ 2023-03-19 17:48:16

修改

if(mx[u]<size[root])
    root=u;

if(mx[u]<mx[root])
    root=u;

这样会导致重心寻找错误,时间复杂度退化


by a_sad_soul @ 2023-03-20 22:51:41

@OIdrearmer_Z 谢谢大佬,一直没看到555


by a_sad_soul @ 2023-03-20 22:55:04

@OIdrearmer_Z 改了,但是好像没有什么用捏


by zjy2008 @ 2023-03-21 08:24:21

@a_sad_soul 抱歉,现在才看到

bool vis[MAXN],judge[MAXXN],ans[MAXN],S;

by a_sad_soul @ 2023-03-21 13:19:13

@OIdrearmer_Z wc什么低级错误,谢谢大佬%%%


|