# bzoj 4756 [Usaco2017 Jan]Promotion Counting

### Description

The cows have once again tried to form a startup company, failing to remember from past experience t
hat cows make terrible managers!The cows, conveniently numbered 1…N1…N (1≤N≤100,000), organize t
he company as a tree, with cow 1 as the president (the root of the tree). Each cow except the presid
ent has a single manager (its “parent” in the tree). Each cow ii has a distinct proficiency rating,
p(i), which describes how good she is at her job. If cow ii is an ancestor (e.g., a manager of a man
ager of a manager) of cow jj, then we say jj is a subordinate of ii.
Unfortunately, the cows find that it is often the case that a manager has less proficiency than seve
ral of her subordinates, in which case the manager should consider promoting some of her subordinate
s. Your task is to help the cows figure out when this is happening. For each cow ii in the company,
please count the number of subordinates jj where p(j)>p(i).
n只奶牛构成了一个树形的公司，每个奶牛有一个能力值pi，1号奶牛为树根。

### Input

The first line of input contains N
The next N lines of input contain the proficiency ratings p(1)…p(N)
for the cows. Each is a distinct integer in the range 1…1,000,000,000
The next N-1 lines describe the manager (parent) for cows 2…N
Recall that cow 1 has no manager, being the president.
n，表示有几只奶牛 n<=100000

### Output

Please print N lines of output. The ith line of output should tell the number of
subordinates of cow ii with higher proficiency than cow i.

5

804289384

846930887

681692778

714636916

957747794

1

1

2

3

2

0

1

0

0

### 题解

#include <cstdio>
#include <algorithm>
#define mid (l + r >> 1)
#define lson t[rt].l, l, mid
#define rson t[rt].r, mid + 1, r
using namespace std;
const int N = 100010;
int a[N], b[N], n, sz, x, root[N], ans[N];
struct edge {
int to, next;
}e[N];
int st[N], tot;
void add(int x, int y) {
e[++tot].next = st[x];
e[tot].to = y, st[x] = tot;
}
struct segt {
int l, r, sum;
}t[N * 20];
void update(int rt) { t[rt].sum = t[t[rt].l].sum + t[t[rt].r].sum; }
void inserts(int pos, int &rt, int l, int r) {
rt = ++sz;
if (l == r) { t[rt].sum = 1; return; }
if (pos <= mid) inserts(pos, lson);
else            inserts(pos, rson);
update(rt);
}
int merges(int x, int y) {
if (!x) return y;
if (!y) return x;
t[x].l = merges(t[x].l, t[y].l);
t[x].r = merges(t[x].r, t[y].r);
update(x); return x;
}
int query(int rt, int l, int r, int L, int R) {
if (L <= l && R >= r) return t[rt].sum;
int ans = 0;
if (L <= mid) ans += query(lson, L, R);
if (R >  mid) ans += query(rson, L, R);
return ans;
}
void dfs(int x) {
for (int i = st[x]; i; i = e[i].next)
dfs(e[i].to), root[x] = merges(root[x], root[e[i].to]);
ans[x] = query(root[x], 1, n, a[x] + 1, b[0]);
}
main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + 1 + n);
b[0] = unique(b + 1, b + 1 + n) - b - 1;
for (int i = 1; i <= n; ++i)
a[i] = lower_bound(b + 1, b + 1 + b[0], a[i]) - b;
//  for (int i = 1; i <= n; ++i)
//      printf("%d ", a[i]);
for (int i = 2; i <= n; ++i)
scanf("%d", &x), add(x, i);
for (int i = 1; i <= n; ++i)
inserts(a[i], root[i], 1, n);
dfs(1);
for (int i = 1; i <= n; ++i)
printf("%d\n", ans[i]);
}