2039. 树的统计

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

新老客户大回馈,云服务器低至5折

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

【题目描述】

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

 

【输入格式】

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

【输出格式】

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

【样例输入】

3
2
3
0

【样例输出】

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     }
复制代码

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P2279 [HNOI2003]消防局的设立

下一篇:[转]RGB数据保存为BMP图片