拓扑+LCA
思路清奇的一道好题
这个题真的不毒瘤！！
吐槽一下出题人如何同时吓死草原上的羊？？
先考虑一下暴力
反向建图跑个拓扑就完事了
考虑一些特殊的情况
假如输入的是一棵树，那么一个点的贡献就是他的子树大小-1，也就是子树中除他以外的所有点，但是大多数情况输入是一个DAG，那我们是不是可以找到一种方法，把它转化成一棵树呢？ 我们考虑样例的情况 不难发现，若是4号点凉了，当且仅当2,3都凉了，而2,3都凉了的情况得建立在1凉了的情况下，也就是说4只会对1凉了这种情况产生贡献，所以我们就可以直接把4挂到1下面，这样就不用管2,3对4的影响了，然后我们考虑 ，对于1个点指向的多个点，1会产生贡献，只有在它的食物，也就是他指向的这一堆点全部凉了的情况下，而这一堆点都凉了，那必然他们的食物也凉了，一直向上推，直到他们只有一个食物，也就是说所有点交在了一起时，这个交点凉了，那么下面也就都凉了，这个点是啥？
是下面所有点在新树上的LCA，但发现有些点没有食物？我们额外建一个0号点，使得所有没没有食物的点的fa=0，这样就会交于一点了 ，我们在原图上跑拓扑，按拓扑序的倒序开始建树，因为他的拓扑序越靠后，那么他在新树上的深度就越浅，因为他被最多的人指了，必然在食物链最底端，然后我们倒序遍历就相当于正序建树了，我们把一个点接到他指向的所有点的LCA上就好了，而他指向的所有点，必然比他先处理了，最后我们dfs求一遍子树大小就好了
代码
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std
;
const int M
=100500;
int n
;
int to
[M
],nxt
[M
],head
[M
],cnt
;
int net
[M
],go
[M
],last
[M
],tot
;
int f
[M
][20],dep
[M
],ti
[M
],in
[M
],ans
[M
];
inline void read(int &x
)
{
x
=0;char ch
=getchar();
while (!isdigit(ch
)) ch
=getchar();
while (isdigit(ch
)) x
=x
*10+ch
-'0',ch
=getchar();
return ;
}
inline void ad1(int x
,int y
)
{
to
[++cnt
]=y
;nxt
[cnt
]=head
[x
];head
[x
]=cnt
;
return ;
}
inline void ad2(int x
,int y
)
{
go
[++tot
]=y
;net
[tot
]=last
[x
];last
[x
]=tot
;
return ;
}
inline void topsort()
{
queue
<int>q
;int t
=0;
for (int i
=1;i
<=n
;i
++)
if (!in
[i
]) q
.push(i
);
while (q
.size())
{
int u
=q
.front();q
.pop();ti
[++t
]=u
;
for (int i
=head
[u
];i
;i
=nxt
[i
])
if (--in
[to
[i
]]==0) q
.push(to
[i
]);
}
return ;
}
inline int lca(int x
,int y
)
{
if (dep
[x
]<dep
[y
]) swap(x
,y
);
for (int i
=18;i
>=0;i
--)
if (dep
[f
[x
][i
]]>=dep
[y
])
x
=f
[x
][i
];
if (x
==y
) return x
;
for (int i
=18;i
>=0;i
--)
if (f
[x
][i
]!=f
[y
][i
])
x
=f
[x
][i
],y
=f
[y
][i
];
return f
[x
][0];
}
inline void built()
{
dep
[0]=1;
memset(last
,-1,sizeof(last
));
for (int i
=n
;i
>=1;i
--)
{
int u
=ti
[i
];
if (head
[u
]==0)
{ad2(0,u
);dep
[u
]=2;continue;}
int l
=to
[head
[u
]];
for (int k
=nxt
[head
[u
]];k
;k
=nxt
[k
])
l
=lca(l
,to
[k
]);ad2(l
,u
);
dep
[u
]=dep
[l
]+1;f
[u
][0]=l
;
for (int k
=1;k
<=18;k
++)
f
[u
][k
]=f
[f
[u
][k
-1]][k
-1];
}
return ;
}
inline void dfs(int x
)
{
ans
[x
]=1;
for (int i
=last
[x
];~i
;i
=net
[i
])
dfs(go
[i
]),ans
[x
]+=ans
[go
[i
]];
return ;
}
signed main()
{
read(n
);int x
;
for (int i
=1;i
<=n
;i
++)
while (1)
{
read(x
);if (!x
) break;
in
[x
]++;ad1(i
,x
);
}
topsort();built();dfs(0);
for (int i
=1;i
<=n
;i
++)
printf("%d\n",ans
[i
]-1);
return 0;
}
