记录编号	372066	评测结果	AAAAAAAAAA
题目名称	树的统计	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.390 s
提交时间	2017-02-17 17:08:59	内存使用	2.21 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 100002
vector<int> G[MAXN];
int n;
int bit[MAXN];
void add(int x, int v){
  for(; x <= n; x += x&-x)bit[x] += v;
}
int query(int x){
  int r = 0;
  for(x--; x; x -= x&-x)r += bit[x];
  return r;
}
int ans[MAXN];
void dfs(int u, int f){
  add(u, 1);
  ans[u] = query(u);
  for(int i = 0; i < G[u].size(); i++){
    if(G[u][i] != f)dfs(G[u][i], u);
  }
  ans[u] = query(u)-ans[u];
}
int main()
{
  freopen("counttree.in", "r", stdin);
  freopen("counttree.out", "w", stdout);
  scanf("%d", &n);
  int r;
  for(int i = 1, f; i <= n; i++){
    scanf("%d", &f);
    if(f){
      G[f].push_back(i); G[i].push_back(f);
    }else r = i;
  }
  dfs(r, 0);
  for(int i = 1; i <= n; i++)printf(i==n?"%d\n":"%d ", ans[i]);
  return 0;
}