2039. 树的统计
输入文件：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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-05-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录