#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)
const int N = 200100;
const int R1 = 510;
const int R2 = 25010;
const int off = 1 << 18;
int tr[off * 4];
int lazy[off * 4];
void prop(int node, int x, int y) {
tr[node] += lazy[node];
if (x != y) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
void update(int l, int r, int delta, int node = 1, int x = 0, int y = off - 1) {
if (x > r or y < l) return;
if (l <= x and y <= r) {
lazy[node] += delta;
prop(node, x, y);
return;
}
prop(node, x, y);
update(l, r, delta, node * 2, x, (x + y) / 2);
update(l, r, delta, node * 2 + 1, (x + y) / 2 + 1, y);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
int query(int l, int r, int node = 1, int x = 0, int y = off - 1) {
if (x > r or y < l) return 0;
prop(node, x, y);
if (l <= x and y <= r) return tr[node];
return query(l, r, node * 2, x, (x + y) / 2) + query(l, r, node * 2 + 1, (x + y) / 2 + 1, y);
}
int n, r, q;
int h[N];
int par[N];
vector<int> chi[N];
vector<int> emp[R2];
int in[N];
int out[N];
int timer;
int cnt[R1][R1];
vector<int>* dfs(int node) {
vector<int>* cur = nullptr;
for (int u : chi[node]) {
vector<int>* v = dfs(u);
if (cur == nullptr) {
cur = v;
} else {
for (int i = 1; i < R1; i++) {
(*cur)[i] += (*v)[i];
}
delete(v);
}
}
if (sz(chi[node]) == 0) {
cur = new vector<int>(R1);
}
for (int i = 1; i < R1; i++) {
cnt[h[node]][i] += (*cur)[i];
}
(*cur)[h[node]]++;
return cur;
}
void dfs2(int node) {
timer++;
in[node] = timer;
for (int u : chi[node]) {
dfs2(u);
}
out[node] = timer;
}
int main() {
FIO;
cin >> n >> r >> q;
for (int i = 1; i <= n; i++) {
if (i != 1) {
cin >> par[i];
chi[par[i]].pb(i);
}
cin >> h[i];
emp[h[i]].pb(i);
}
if (r <= 500) {
dfs(1);
for (int i = 0; i < q; i++) {
int r1, r2;
cin >> r1 >> r2;
int ans = cnt[r1][r2];
cout << ans << endl;
}
} else {
dfs2(1);
for (int i = 0; i < q; i++) {
int r1, r2;
cin >> r1 >> r2;
for (int x : emp[r1]) {
update(in[x], out[x], 1);
}
int ans = 0;
for (int x : emp[r2]) {
ans += query(in[x], in[x]);
}
for (int x : emp[r1]) {
update(in[x], out[x], -1);
}
cout << ans << endl;
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |