★★ 輸入文件：counttree.in 輸出文件：counttree.out 簡單對比 時間限制：1 s 記憶體限制：128 MB 【題目描述】 【輸入格式】 輸入第一行包含一個整數N，以下N行每行包含一個整數，其中第i行的整數表示編號為i的節點的父親節點的編號，根的父親節點編號為0。 【輸出格式】 ...
★★ 輸入文件：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 }
