为什么把超级源点设成 0 第 5 个点会 WA,而设成 n+1 就 AC 了?
#include<bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
inline int read()
{
int res=0;
bool op=0;
char ch=getchar();
while(!isdigit(ch))
{
op|=ch=='-';
ch=getchar();
}
while(isdigit(ch))
{
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
return op?-res:res;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
int n,in[65540],out[65440],d[65440],fa[65440][18],ans[65440];
vector<int>s1[65540],s2[65440];
inline int lca(int x,int y)
{
if(d[x]<d[y]) swap(x,y);
for(re int i=17;~i;--i) if((d[x]-d[y])>>i&1) x=fa[x][i];
if(x==y) return x;
for(re int i=17;~i;--i)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int main()
{
n=read();
for(re int i=1;i<=n;++i)
{
int x=read();
while(x)
{
s1[x].push_back(i);
s2[i].push_back(x);
++in[i];
++out[x];
x=read();
}
}
queue<int>q;
for(re int i=1;i<=n;++i) if(!in[i]) q.push(i);
while(q.size())
{
int u=q.front(),x=0;
q.pop();
for(re int i=0;i<s2[u].size();++i)
{
int v=s2[u][i];
if(!x) x=v;
else x=lca(x,v);
}
if(!x) x=n+1;//一开始是 $0$
fa[u][0]=x;
d[u]=d[x]+1;
for(re int i=1;i<18;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
for(re int i=0;i<s1[u].size();++i)
{
int v=s1[u][i];
--in[v];
if(!in[v]) q.push(v);
}
}
for(re int i=1;i<=n;++i)
{
if(!out[i]) q.push(i);
ans[i]=1;
}
while(q.size())
{
int u=q.front();
q.pop();
ans[fa[u][0]]+=ans[u];
for(re int i=0;i<s2[u].size();++i)
{
int v=s2[u][i];
--out[v];
if(!out[v]) q.push(v);
}
}
for(re int i=1;i<=n;++i)
{
write(ans[i]-1);
puts("");
}
return 0;
}