只过了2345测试点,其他全WA了,请帮忙看一下ToT
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define MAXN 65550
#define MAXLOG 21
using namespace std;
vector<int>g[MAXN];
vector<int>tree[MAXN];
vector<int>ug[MAXN];
queue<int>q;
int n,tmpb,in[MAXN],now,d[MAXN]{1},xu[MAXN],xuk=-1,f[MAXN][MAXLOG],size[MAXN];
inline static void link(int x,int y){
g[x].push_back(y);
ug[y].push_back(x);
in[y]++;
}
inline static void addson(int x,int fa){
tree[fa].push_back(x);
f[x][0]=fa;
d[x]=d[fa]+1;
for(int k=1;k<MAXLOG;k++){
f[x][k]=f[f[x][k-1]][k-1];
}
}
inline static void tuopu(){
for(int i=1;i<=n;i++){
if(!in[i]){
link(0,i);
}
}
q.push(0);
while(!q.empty()){
now=q.front();
q.pop();
xu[++xuk]=now;
for(vector<int>::iterator it=g[now].begin();it<g[now].end();it++){
if(!(--in[*it])){
q.push(*it);
}
}
}
}
inline static int get_lca(int x,int y){
if(x==-1)return y;
if(d[x]<d[y])swap(x,y);
for(int i=MAXLOG;i>=0;i--){
if(d[f[x][i]]>=d[y])x=f[x][i];
}
if(x==y)return x;
for(int i=MAXLOG-1;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i],y=f[y][i];
}
}
return f[x][0];
}
inline static void build_tree(){
for(int i=1;i<=xuk;i++){
int lca=-1;
for(vector<int>::iterator it=ug[xu[i]].begin();it<ug[xu[i]].end();it++){
lca=get_lca(lca,*it);
}
addson(xu[i],lca);
}
}
inline static void dfs(int x){
size[x]=1;
for(vector<int>::iterator it=tree[x].begin();it<tree[x].end();it++){
dfs(*it);
size[x]+=size[*it];
}
}
int main(){
freopen("P2597_1.in","r",stdin);
freopen("P2597_1.txt","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&tmpb);
if(tmpb){
link(tmpb,i);
}
else break;
}
}
tuopu();
build_tree();
dfs(0);
for(int i=1;i<=n;i++){
printf("%d\n",size[i]-1);
}
return 0;
}