这种问题的转化方式挺巧妙的.

Code:

#include <bits/stdc++.h>
#define N 100000
#define M 1000000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
queue<int>q;
vector<int>G,V[N];
int n,root,edges;
int fa[20][N],hd[N],to[M],nex[M],deg[N],sum[N],dep[N];
void add(int u,int v)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,++deg[v];
}
void toposort()
{
for(int i=1;i<=n+1;++i) if(deg[i]==0) q.push(i), G.push_back(i);
for(;!q.empty();)
{
int u=q.front();q.pop();
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
--deg[v];
if(deg[v]==0) q.push(v), G.push_back(v);
}
}
}
int LCA(int x,int y)
{
if(dep[x]>dep[y]) swap(x,y); // dep of y is greater than dep of x
if(dep[x]!=dep[y])
{
for(int i=18;i>=0;--i) if(dep[fa[i][y]]>=dep[x]) y=fa[i][y];
}
if(x==y) return x;
for(int i=18;i>=0;--i)
{
if(fa[i][x]!=fa[i][y])
{
x=fa[i][x],y=fa[i][y];
}
}
return fa[0][x];
}
void dfs(int u)
{
sum[u]=1;
for(int i=0;i<V[u].size();++i)
{
int v=V[u][i];
dfs(v);
sum[u]+=sum[v];
}
}
int main()
{
int i,j;
// setIO("input");
scanf("%d",&n);
root=n+1;
for(i=1;i<=n;++i)
{
int t;
scanf("%d",&t);
if(!t) add(i,root);
else for(;t!=0;scanf("%d",&t)) add(i,t);
}
toposort();
dep[n+1]=1;
for(i=G.size()-2;i>=0;--i)
{
int u=G[i];
int lca=to[hd[u]];
for(j=nex[hd[u]];j;j=nex[j]) lca=LCA(lca, to[j]);
fa[0][u]=lca;
dep[u]=dep[lca]+1;
V[lca].push_back(u);
for(j=1;j<=18;++j) fa[j][u]=fa[j-1][fa[j-1][u]];
}
dfs(root);
for(i=1;i<=n;++i) printf("%d\n",sum[i]-1);
return 0;
}

  

最新文章

  1. win10调用局域网内xp系统上的打印机
  2. 《JavaScript DOM编程艺术》笔记一
  3. 【AT91SAM3S】ADC中断方式采集数据
  4. JavaScript闭包的底层运行机制
  5. Java导入证书失败Keystore was tampered with, or password was incorrect
  6. 扯扯maven的蛋
  7. (简单) POJ 3279 Fliptile,集合枚举。
  8. 微信小程序之----消息提示框toast
  9. Pycharm直接连接Github
  10. 来聊一聊不low的Linux命令——find、grep、awk、sed
  11. 014_IP专项研究监控
  12. python是c语言开发的
  13. Effective STL 学习笔记 Item 17: Swap Trick
  14. 跟着百度学习php之ThinkPHP的运行流程-1
  15. D. Two Paths---cf14D(树的直径)
  16. django views.py视图 获取用户请求相关信息以及请求头
  17. 28UDP
  18. 反省在北京某S2B2C电商小型公司面试时掉链子的问题
  19. Android Dagger2.0 学习一下
  20. react-event-pooling

热门文章

  1. [游戏复刻] Super Mario Brothers(1985. Famicom)
  2. 【静态延迟加载】self关键字和static关键字的区别
  3. python3启航
  4. Java 并发进阶常见面试题总结
  5. Lambda表达式使用方法整理
  6. CORE EF生成ORACLE数据库模型报错问题记录
  7. 二元变量图形的pandas方法
  8. base64转换成文件图片
  9. java Calendar Date 获取指定日期所在月或年的第一天和最后一天
  10. jumperver源码理解以及部分修改