按照出题人的题解，我们需要构造一颗“灭绝树”。即对于灭绝树上的两个点x，y，如果x为y的祖先，则x的灭亡会直接导致y的灭亡。下面进行构造：
首先进行拓扑排序，然后按照排序的逆序构造，保证对于图中的任意x->{y}，都能使x构造前，{y}已经完成构造。然后找到{y}在灭绝树上面的位置，显然{y}在灭绝树上的公共祖先的灭绝会导致{y}全部灭绝进而导致x灭绝。于是可以求它们的lca，那么lca就是x在灭绝树上面的祖先。最后跑一边dfs统计子树大小即可。
实际上，这是求有向图必经点的一个特殊问题（无环），实际上可以直接用支配树解决（然而窝太弱不会）。也是O(N)级别的。
AC代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
int n,m,tot,sz[N],h[N],bin[20],pnt[N<<4],nxt[N<<4],d[N],fa[N][17],etr[N];
int read(){
int x=0; char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
return x;
}
int lca(int x,int y){
if (x<0) return y;
if (d[x]<d[y]) swap(x,y); int tmp=d[x]-d[y],i;
for (i=0; i<17; i++)
if (tmp&bin[i]) x=fa[x][i];
for (i=16; ~i; i--)
if (fa[x][i]!=fa[y][i]){ x=fa[x][i]; y=fa[y][i]; }
return (x==y)?x:fa[x][0];
}
struct node{
int fst[N];
void add(int x,int y){
pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot; etr[y]++;
}
void topo(){
int head=0,tail=0,i;
for (i=1; i<=n; i++) if (!etr[i]) h[++tail]=i;
while (head<tail){
int x=h[++head],p;
for (p=fst[x]; p; p=nxt[p]){
int y=pnt[p]; etr[y]--;
if (!etr[y]) h[++tail]=y;
}
}
}
void extend(int x,int y){
add(x,y); d[y]=d[x]+1; fa[y][0]=x; int i;
for (i=1; i<17; i++) fa[y][i]=fa[fa[y][i-1]][i-1];
}
void dfs(int x){
sz[x]=1; int p;
for (p=fst[x]; p; p=nxt[p]){
dfs(pnt[p]); sz[x]+=sz[pnt[p]];
}
}
}g1,g2;
void build(){
int i; bin[0]=1;
for (i=1; i<17; i++) bin[i]=bin[i-1]<<1;
for (i=n; i; i--){
int x=h[i],p,tmp=-1;
for (p=g1.fst[x]; p; p=nxt[p])
tmp=lca(tmp,pnt[p]);
g2.extend(max(tmp,0),x);
}
}
int main(){
n=read(); int i;
for (i=1; i<=n; i++){
int x=read();
for (; x; x=read()) g1.add(i,x);
}
g1.topo(); build(); g2.dfs(0);
for (i=1; i<=n; i++) printf("%d\n",sz[i]-1);
return 0;
}
by lych
2016.2.26
文章浏览阅读449次。在之前的文章编写过程中，插入JS代码后，第一次文章会显示正常，而之后在后台编辑器中再打开看, 发现好多标签竟然被删掉了。后来发现解决办法非常简单。我们在插入代码后，源码模式下，看起来是正常的，但是为什么保存完之后，数据库中正常，但是编辑器中不正常呢？很多富文本编辑器都有两种初始化方式，以UEditor为例，一种是textarea标签，一种是script标签。举例textarea方式：这里写你的初始..._百度富文本编辑器过滤了html标签
文章浏览阅读661次，点赞6次，收藏20次。最后还准备了一套上面资料对应的面试题（有答案哦）和面试时的高频面试算法题（如果面试准备时间不够，那么集中把这些算法题做完即可，命中率高达85%+）份系统化的资料的朋友，可以添加V获取：vip1024b （备注Java）**(img-0bihoba1-1713545040863)]JAVA相关笔试题，祝各位找到好工作！Java网络安全面试题系列。
文章浏览阅读1.1w次，点赞9次，收藏36次。Latex 反斜对角省略号_latex 省略号
文章浏览阅读5.7k次。1 importio2 importos3 importre4 importsys5 importdatetime6 from bs4 importBeautifulSoup7 from pxydowwload importrequest8 from pymongo importMongoClient910 sys.stdout = io.TextIOWrapper(sys.stdout.buff..._mzitu
文章浏览阅读170次。2020/06/01 面向对象编程面向对象（object oriented programming，OOP）编程的思想主要是针对大型软件设计而来的。面向对象编程使程序的扩展性更强、可读性更好，使得编程可以像搭积木一样简单。Python中一切皆对象。Python支持面向过程、面向对象、函数式编程等多种编程范式。面向对象和面向过程的区别面向过程思维：更加关注的是“程序的逻辑流程”，是一种“执行者”思维，适合编写小规模的程序。面向对象思维：更加关注的是“软件中对象之间的关系”，是一种“设计者”思维_python从入门到入坟
文章浏览阅读4.1w次，点赞12次，收藏14次。案例：绘制多个同心圆代码如下：import turtlet = turtle.Pen()my_colors = ("red", "green", "yellow", "black")t.width(4)t.speed(1)for i in range(10): # 0 1 2 3 4 t.penup() t.goto(0, -i*10) # 0, -100,-2..._python利用负循环画10个同心圆
文章浏览阅读1.6k次。该楼层疑似违规已被系统折叠隐藏此楼查看此楼大三下学期NO.1Web数据库技术(3`)专业必修课本学期最难一科，考题是默写程序！填空(通常得不到几分)简答，程序。考前认真复习，课上不上无所谓，最终你还是要背的。重点：第三章：链接herf(填空)，登陆表单(html程序题，可以参考习题1)登陆表单验证(JavaScript程序题 P30)第四章：脚本段-表达式-声明-指令的区别(简答)，指令元素(简..._编译原理难度排第几
文章浏览阅读2.2k次。一般是uni-app项目使用ucharts在原生微信小程序也是可以使用。方法：## 使用说明请将项目根目录 微信小程序/uCharts-组件/qiun-wx-ucharts/src 下全部文件复制到指定位置，例如该项目的components/qiun-wx-uchart目录下，然后在页面的json配置文件中配置如下：配置好后即可在wxml文件中使用注：示例中uCharts组件仅做演示，实际使用请用码云或者npmjs中最新版本。_微信小程序引入ucharts
文章浏览阅读1.3k次。关于内容来源于微信公众号：大神编程。已经过原文作者授权。题目：1095：数1的个数超详细动画图文题解链接题解目录（不断更新中）喜欢信息学奥赛的同学们，可以一起交流学习哦官方QQ群：893157498我的QQ群：795233394..._y1095 数1的个数
文章浏览阅读220次。line-height: 设置元素当中的每行文本的行高（行间距） .test { width: 300px; height: 40px; margin-bottom: 20px; padding: 10px; background-color:..._段落元素设置样式
文章浏览阅读1.3k次。目标：使用OpenCV cv::inRange 函数进行基本的 阈值操作， 基于像素值在HSV色度空间的范围进行对象检测理论：前一篇文章中我们学习了如何使用cv::threshold 阈值函数进行阈值操作 本文我们将学习使用 cv::inRange 来进行处理 原理是一样的但是现在我们增加了一个我们所需要的 【像素值的范围】HSV色度空间 HSV colorspaceHSV ..._inrange和cv2.threshold一起使用
文章浏览阅读154次。 瑜伽培训课程层出不穷，但市面上都没有教授瑜伽老师们如何“教”的系统培训。瑜伽行业表面看似繁荣，但大多数老师缺失教学的“灵魂”。 为此，心合瑜伽学院王梓涵院长结合多年来积累的经验以及瑜伽老师的痛点，与心合教学团队不断打磨，开创瑜伽培训先河，首创贴合瑜伽老师的『瑜伽教学法』，教学法正是指导瑜伽老师们如何上课的法门！ 不少老师们，有时会有这样的问题： “我把正确的口令讲出来了，但是会员好像不听我的口令，并没有按照口令去做，需要我不停地辅助和做示范才能完成...” 一个优秀的老师，总可以_会员病了无法来上瑜伽课怎么说