Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

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

const int N = (int) 1e5;
vector<int> children[N];
int inTime[N];
int outTime[N];
int salary[N];
int subsize[N];
int boss[N];
int bit[N];
int cnt[N];

void update(int x, int a) {
    while (x < N) {
        bit[x] += a;
        x |= x + 1;
    }
}

int get(int x) {
    int result = 0;
    while (x >= 0) {
        result += bit[x];
        x -= ~x & (x + 1);
    }
    return result;
}

int main() {
#ifdef __DNK__
    assert(freopen("salary.in", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    int n; cin >> n >> salary[0];
    boss[0] = -1;
    for (int i = 1; i < n; ++i) {
        cin >> boss[i] >> salary[i];
        --boss[i];
        children[boss[i]].push_back(i);
    }
    for (int i = n - 1; i >= 0; --i) {
        ++subsize[i];
        if (boss[i] != -1) subsize[boss[i]] += subsize[i];
    }
    queue<int> q;
    q.push(0);
    inTime[0] = 0;
    outTime[0] = n;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int cur = inTime[u] + 1;
        for (int v : children[u]) {
            inTime[v] = cur;
            cur += subsize[v];
            outTime[v] = cur;
            q.push(v);
        }
    }
    vector<int> order (n);
    for (int i = 0; i < n; ++i) order[i] = i;
    sort(order.begin(), order.end(), [] (int x, int y) {
            return salary[x] != salary[y] ? salary[x] < salary[y] : x < y;
            });
    long long result = 0;
    for (int u : order) {
        long long tmp = get(outTime[u] - 1) - get(inTime[u] - 1);
        result += tmp * (tmp - 1) / 2;
        update(inTime[u], 1);
    }
    cout << result << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

const int N = 100005;

using namespace std;

int n;
int Time;
int par[N];
int c[N], cost[N];
int L[N], R[N];
vector<int> child[N];

struct node {
    int l, r;
    int *V;
    node *left, *right;

    node(int _l, int _r) {
        l = _l; r = _r;
        V = new int[r - l + 1];
        left = right = NULL;
    }

    inline int size() {
        return r - l + 1;
    }

    int query(int i, int j, int k) {
        if (r < i || j < l) return 0;
        if (i <= l && r <= j)
            return lower_bound(V, V + size(), k) - V;
        return left->query(i, j, k) + right->query(i, j, k);
    }
};

node *build(int l, int r) {
    if (l > r) return NULL;
    node *x = new node(l, r);
    if (l == r) {
        x->V[0] = cost[l];
        return x;
    }
    x->left = build(l, l + r >> 1);
    x->right = build((l + r >> 1) + 1, r);
    merge(x->left->V, x->left->V + x->left->size(), x->right->V, x->right->V + x->right->size(), x->V);
    return x;
}

void dfs(int u) {
    L[u] = ++Time;
    cost[Time] = c[u];
    for (int v: child[u])
        dfs(v);
    R[u] = Time;
}

long long comb(long long x) {
    return x * (x - 1) >> 1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifdef _LAD_
    freopen("VMSALARY.txt", "r", stdin);
#endif
    cin >> n >> c[1];
    for (int i = 2; i <= n; ++i) {
        cin >> par[i] >> c[i];
        child[par[i]].push_back(i);
    }
    dfs(1);
    assert(Time == n);
    node *root = build(1, n);
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        int x = root->query(L[i], R[i], c[i]);
        ans += comb(x);
    }
    cout << ans << endl;
    return 0;
}