大佬帮忙康康这个代码,对肯定是对的,就是有一部分点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;
}