#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ll int
typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef map<ll,ll> mll;
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll maxn = 2e5 + 6, maxr = 25e3 + 6, maxb = sqrt(25e3) + 6, mod = 1e9 + 7;
ll n, m, r, k, q, ans, a[maxn], block;
vll adj[maxn];
ll tin[maxn], tout[maxn], tour[maxn], timer = 0;
void dfs(ll p, ll u) {
tin[u] = ++timer;
tour[timer] = u;
for (ll v : adj[u]) {
if (v == p) continue;
dfs(u,v);
}
tout[u] = timer;
}
vll v[maxn], mp[maxn];
ll get(ll l, ll r, ll k) {
auto &v = mp[k];
return upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
}
vll heavy = {0};
ll pos[maxn], freq[maxn], f[maxb][maxr];
void preprocess() {
for (int i = 1; i <= n; ++i) ++freq[a[i]];
for (int i = 1; i <= r; ++i) {
if (freq[i] <= block) continue;
pos[i] = heavy.size();
heavy.push_back(i);
}
//for (ll i : heavy) cout << i << " "; cout << endl;
m = heavy.size() - 1;
for (int i = 1; i <= n; ++i) v[a[i]].push_back(i);
for (int i = 1; i <= n; ++i) mp[a[tour[i]]].push_back(i);
for (int i = 1; i <= m; ++i) {
//cout << "i: " << heavy[i] << endl;
for (int j = 1; j <= r; ++j) {
ll res = 0;
for (ll node : v[heavy[i]]) res += get(tin[node], tout[node], j);
f[i][j] = res;
//cout << "j: " << j << " " << f[i][j] << endl;
}
}
}
void solve() {
cin >> n >> r >> q;
block = sqrt(r);
cin >> a[1];
for (int i = 2; i <= n; ++i) {
ll y;
cin >> y >> a[i];
adj[i].push_back(y);
adj[y].push_back(i);
}
dfs(-1,1);
preprocess();
//for (int i = 1; i <= n; ++i) cout << a[tour[i]] << " "; cout << endl;
// for (int i = 1; i <= r; ++i) {
// cout << i << ": ";
// for (ll j : v[i]) cout << j << " "; cout << endl;
// }
while (q--) {
ll x, y;
cin >> x >> y;
if (freq[x] > block) {
//cout << "HEAVY\n";
cout << f[pos[x]][y] << endl;
} else {
//cout << "LIGHT\n";
ll ans = 0;
for (auto node : v[x]) ans += get(tin[node], tout[node], y);
cout << ans << endl;
}
}
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(".INP", "r")) {
freopen(".INP", "r", stdin);
freopen(".OUT", "w", stdout);
}
ll testCase = 1;
// cin >> testCase;
while (testCase--) {
solve();
}
return 0;
}
Compilation message (stderr)
regions.cpp: In function 'int main()':
regions.cpp:89:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | freopen(".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:90:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | freopen(".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |