COGS 2039. 树的统计

2039. 树的统计

★★ 输入文件：counttree.in 输出文件：counttree.out 简单对比
时间限制：1 s 内存限制：128 MB

【题目描述】

关于树的统计问题有多种多样的版本，这里你需要解决一个比较简单的问题：对于一棵包含N个节点的有根树，将所有点从1到N编号后，对于每一个节点v，统计出以v为根的子树中有多少个点的编号比v小。

【输入格式】

输入第一行包含一个整数N，以下N行每行包含一个整数，其中第i行的整数表示编号为i的节点的父亲节点的编号，根的父亲节点编号为0。

【输出格式】

输出包含N行，其中第i行给出编号为i的节点的统计结果。

【样例输入】

【样例输出】

0 1 2

【提示】

在此键入。

【来源】

20%的数据1<=n<=1000

100%的数据1<=n<=100000

暴力，找出所有最底下的点（也就是叶节点），有叶节点往上不断找到祖先，如果祖先的序号比他小，那么祖先这个点的ans就++，找这个点时可以用拓扑排序。

 1 #include<cstdio>
 2 #include<queue>
 3 using namespace std;
 4  
 5 const int N = 100100;
 6  
 7 queue<int>q;
 8 int fa[N];    //记录父亲 
 9 int ans[N];    
10 int ru[N];    //记录入度 
11 int n,d,now;
12  
13 void sove()
14 {
15     for(int i=1;i<=n;++i)
16         if(ru[i]==0) q.push(i);
17     while(!q.empty())
18     {
19         d = q.front();
20         q.pop();
21         now = d;
22         while(fa[now])
23         {
24             now = fa[now];
25             if(d < now) ans[now]++;
26         }
27         ru[fa[d]]--;
28         if(ru[fa[d]]==0) q.push(fa[d]);
29     }
30 }
31  
32 int main()
33 {
34     freopen("counttree.in","r",stdin);
35     freopen("counttree.out","w",stdout);
36     scanf("%d",&n);
37     for(int i=1;i<=n;++i)
38     {
39         scanf("%d",&fa[i]);
40         ru[fa[i]]++;
41     }
42     sove();
43     for(int i=1;i<=n;++i)
44         printf("%d
",ans[i]);
45     return 0;
46 }