【BZOJ2815】【ZJOI2012】灾难

题目大意:给你一张有向无环图,问去掉各个点后会使多少个点变得入度为0(原来入度就为0的不计)。

最终目标是要构建出一颗树,暂且称它为灾难树。。当一个点的任意一个祖先节点“灭亡”后这个点就会灭亡。于是一个点的灾难值就等于它的子树所含结点数。

所以就可以这样做:按拓扑序,对于每个点,找到所有能吃它的点(因为是按拓扑序进行的,所以它们肯定已经加入了灾难树),求它们在灾难树中的LCA。则这个LCA灭亡时该点灭亡。那么就把这个点接到LCA下面,同时维护一下灾难树的LCA就可以了。

然后就是有个猥琐的数据是一条链,会爆系统栈。。于是我手写了个栈。。然后本地过了但是bzoj还是RE。。不知道为什么了。

说点什么

您将是第一位评论人!

提醒
wpDiscuz