Cod sursă (job #816434)

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("complexat.in");
ofstream cout("complexat.out");

const int Nmax = 300005;

struct nod{
    int val, parinte, cate_mai_mari;
    int timp_inceput, timp_sfarsit;
    vector<int> fii;
};

int n, root, timp;
int aib[2 * Nmax], liniarizare[2 * Nmax];
int indici_sortati[Nmax];
nod arbore[Nmax];

int lsb(int x){
    return (x & (-x));
}

void aib_update(int poz, int val){
    if(poz == 0){
        return;
    }

    for(int i = poz; i <= timp; i += lsb(i)){
        aib[i] += val;
    }
}

int aib_query(int poz){
    int sum = 0;

    for(int i = poz; i > 0; i -= lsb(i)){
        sum += aib[i];
    }

    return sum;
}

int aib_query_interval(int st, int dr){
    return aib_query(dr) - aib_query(st - 1);
}

void citire(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arbore[i].val;
        arbore[i].cate_mai_mari = 0;
    }

    for(int i = 1; i <= n; i++){
        cin >> arbore[i].parinte;

        if(arbore[i].parinte){
            arbore[arbore[i].parinte].fii.push_back(i);
        }
        else{
            root = i;
        }
    }
}

void liniarizare_euler(int nod){
    liniarizare[++timp] = nod;
    arbore[nod].timp_inceput = arbore[nod].timp_sfarsit = timp;

    for(int fiu : arbore[nod].fii){
        liniarizare_euler(fiu);
        liniarizare[++timp] = nod;
        arbore[nod].timp_sfarsit = timp;
    }
}

bool cmp(int ind1, int ind2){
    return arbore[ind1].val > arbore[ind2].val;
}

void sortare_indici(){
    for(int i = 1; i <= n; i++){
        indici_sortati[i] = i;
    }

    sort(indici_sortati + 1, indici_sortati + n + 1, cmp);
}

void calculare_solutii(){
    int indice;

    for(int i = 1; i <= n; i++){
        indice = indici_sortati[i];
        arbore[indice].cate_mai_mari = aib_query_interval(arbore[indice].timp_inceput, arbore[indice].timp_sfarsit);

        aib_update(arbore[indici_sortati[i]].timp_inceput, 1);
        for(int j = i; j >= 1 && arbore[indici_sortati[j]].val == arbore[indici_sortati[j - 1]].val; j--){
            aib_update(arbore[indici_sortati[j - 1]].timp_inceput, 1);
        }
    }
}

void afisare(){
    for(int i = 1; i <= n; i++){
        cout << arbore[i].cate_mai_mari << ' ';
    }
}

int main(){
    citire();

    timp = 0;
    liniarizare_euler(root);

    sortare_indici();
    calculare_solutii();

    afisare();

    return 0;
}