USACO17JAN01 (using node merging)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define pb push_back
#define f first
#define s second

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) FOR(i, 0, a)

const int MAX = 100005;
const int MOD = 1000000007;

template <typename T>
std::ostream& operator<< (std::ostream& out, const std::vector<T>& v) {
  if ( !v.empty() ) {
    out << '[';
    std::copy (v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}


struct BIT {
    int t[MAX];
    void reset() { F0R(i, MAX) { t[i] = 0; } }
    void upd(int i, int v) { for(;i<MAX;i+=(i&(-i))) { t[i]+=v; } }
    int get(int i) { int a = 0; for(;i>0; i-=i&(-i)) { a+=t[i]; } return a; }
};

vi g[MAX];

int sz[MAX], st[MAX], fi[MAX], t[2*MAX];
int ct = 1;
void dfssz(int u, int p) {
    t[ct] = u; st[u] = ct++;
    sz[u] = 1;
    for (int i : g[u]) {
        dfssz(i, u); sz[u] += sz[i];
    }
    fi[u] = ct++;
}

BIT b;
int prof[MAX], cnt[MAX], ans[MAX];
void dfs(int u, int p, bool keep) {
    int maxi = -1, big = -1;
    for (int i : g[u]) {
        if (sz[i] > maxi) {
            maxi = sz[i]; big = i;
        }
    }
    for (int i : g[u]) {
        if (i != big) { dfs(i, u, 0); }
    }
    if (big != -1) { dfs(big, u, 1); }
    for (int i : g[u]) {
        if (i != big) {
            FOR(j, st[i], fi[i]+1) {
                if (t[j] == 0) { continue; }
                b.upd(prof[t[j]], 1);
            }
        }
    }

    b.upd(prof[u], 1);
    ans[u] = sz[u] - b.get(prof[u]);
    if (keep == 0) {
        FOR(j, st[u], fi[u]+1) {
            if (t[j] == 0) { continue; }
            b.upd(prof[t[j]], -1);
        }
    }
}
int main() {
    freopen("promote.in", "r", stdin);
    freopen("promote.out", "w", stdout);
    int n; scanf("%d", &n);
    vector<int> v;
    F0R(i, n) { scanf("%d", &prof[i+1]); v.pb(prof[i+1]); }
    sort(v.begin(), v.end());
    v.resize(distance(v.begin(),unique(v.begin(), v.end())));
    FOR(i, 1, n+1) { prof[i] = lower_bound(v.begin(), v.end(), prof[i]) - v.begin() + 1; }
    FOR(i, 2, n+1) {
        int u; scanf("%d", &u);
        g[u].pb(i);
    }
    dfssz(1, 0);
    dfs(1, 0, 0);
    FOR(i, 1, n+1) { printf("%d\n", ans[i]); }
}