代码诡异re
查看原帖
代码诡异re
120340
lc_lca楼主2020/6/1 20:14

大佬帮忙康康这个代码,对肯定是对的,就是有一部分点re,想知道为啥,谢谢!

能告诉juruo哪些地方会出现re的可能就好了,感谢!

#include<iostream>
#include<cstring>
#include<set>
#define int long long
using namespace std;
const int maxn=200010;
struct node{
    int v,w,nxt;
}edge[maxn<<1];
int head[maxn],tot;
int maxx;
void addedge(int u,int v,int w)
{
    edge[tot].v=v;
    edge[tot].w=w;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}
void init()
{
    memset(head,-1,sizeof head);
    tot=0;
}
int n,d,dep[maxn];
int f[maxn];
int dis[maxn];
void dfs(int u,int pre)
{
    if(u==1) dep[u]=0;
    else dep[u]=dep[pre]+1;
    f[u]=pre;
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==pre) continue;
        dfs(v,u);
        dis[v]=edge[i].w;
    }
}
set<pair<int,int> >st;
void D(int x)
{
    st.erase(make_pair(-dep[x],x));
}
int vis[maxn];
int A[maxn];
void delson(int u,int pre,int top,int len,int avoid,int maxlen,int add)
{
    if(len>=maxlen)
    {
        addedge(top,u,len+add);
        addedge(u,top,len+add);
        return;
    }
    //cout<<"del:"<<u<<endl;
    D(u);
    vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==pre || vis[v] || v==avoid) continue;
        delson(v,u,top,len+edge[i].w,avoid,maxlen,add);
    }
}
void Del(int u,int pre,int avoid)
{
    int tmpp=u;
    int sum=0;
    A[u]=0;
    while(true)
    {
        if(f[tmpp]==0)
        {
            break;
        }
        sum+=dis[tmpp];
        tmpp=f[tmpp];
        if(sum>=d) break;
        A[tmpp]=sum;
    }
    int totsum=sum;
    int topp=tmpp;
    delson(u,f[u],topp,0,avoid,d,A[topp]);
    //cout<<"---------"<<endl;
    sum=0;
    while(true)
    {
        int tmp=u;
        sum+=dis[tmp];
        u=f[u];
        if(sum>=d) break;
        //cout<<"u="<<u<<" f[u]="<<f[u]<<" avoid:"<<tmp<<" maxlen="<<d-sum<<" add="<<totsum-A[u]<<endl;
        delson(u,f[u],topp,0,tmp,d-sum,totsum-A[u]);
        if(f[u]==0) break;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    init();
    cin>>n>>d;
    for(int i=1;i<n;i++)
    {
        int lc;
        cin>>lc;
        addedge(lc+1,i+1,1);
        addedge(i+1,lc+1,1);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        st.insert(make_pair(-dep[i],i));
    }
    int res=0;
    while(1)
    {
        if(st.empty()) break;
        pair<int,int> Begin=*st.begin();
        st.erase(Begin);
        int u=Begin.second;
        res++;
        Del(u,0,-1);
    }
    cout<<res<<endl;
    return 0;
}

2020/6/1 20:14
加载中...