首页 > > 程序设计 > C/C++ >

2039. 树的统计

2018-06-17 22:29:54来源：未知阅读 ()

★★ 输入文件：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

上来看了一眼题目难度是两颗黑星，感觉十分不可做（因为我一般在cogs刷两星的题目很少一遍不看题解AC）

一开始以为是树上倍增.树上DP.RMQ之类的，但是都不会啊。。

无奈只能暴力。

暴力思路：

一：读入每一个点，记录他的father，

二：枚举每一个点，如果他的father不为0且它的father的值比他大，那么它的father的值就++

正解：

DFS序+树状数组

但是看了一下评测记录我的暴力0.125s秒杀所有正解+暴力=.=

 1     #include<iostream>
 2     #include<cstdio>
 3     #include<cstring>
 4     #include<cmath>
 5     using namespace std;
 6     const int MAXN=100001;
 7     int read(int & n)
 8     {
 9         char c='/';int x=0,flag=0;
10         while(c<'0'||c>'9')
11         {c=getchar();
12         if(c=='-')flag=1;}
13         while(c>='0'&&c<='9')
14         {x=x*10+c-48;c=getchar();}
15         if(flag)n=-x;
16         else n=x;
17         return n;
18     }
19     int n,p;
20     int fa[MAXN];
21     int ch[MAXN];
22     int num[MAXN];
23     int main()
24     {
25         freopen("counttree.in","r",stdin);
26         freopen("counttree.out","w",stdout);
27         read(n);
28         for(int i=1;i<=n;i++)
29         {
30             read(p);
31             fa[i]=p;    
32         }
33         for(int i=1;i<=n;i++)
34         {
35             int p=i;
36             while(fa[p]!=0)
37             {
38                 if(fa[p]>i)
39                     num[fa[p]]++;
40                 p=fa[p];
41             }
42         }
43         for(int i=1;i<=n;i++)
44         {
45             printf("%d ",num[i]);
46         }
47         return 0;
48     }