| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1285047 | souvenir_vayne | Regions (IOI09_regions) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <chrono>
#define pb push_back
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define fin cin
#define fout cout
#define s second
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define debug(x) cerr << "DEBUG " << x << endl
#define debug2(x, y) cerr << "DEBUG " << x << " " << y << endl
#define debug3(x, y, z) cerr << "DEBUG " << x << " " << y << " " << z << endl
#define debug4(x, y, z, o) cerr << "DEBUG " << x << " " << y << " " << z << " " << o << endl
#define all(x) x.begin(), x.end()
#define left esquerda
#define lb lower_bound
#define right direita
using namespace std;
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
typedef pair<ll, ll> pii;
typedef vector<vector<char>> mat;
typedef pair<int, string> pis;
const ll mod = 1e9 + 7, MAXN = 2e5 + 5;
typedef vector<int> vi;
typedef pair<int, pair<int, int>> piii;
ll seg[MAXN << 2];
void update(int u, int l, int r, int k, int x) {
if(l > k or r < k)
return;
if(l == r) {
seg[u] = x;
return;
}
int mid = (l+r)/2;
update(2*u, l, mid, k, x);
update(2*u+1, mid+1, r, k, x);
seg[u] = seg[2*u] + seg[2*u+1];
return;
}
ll query(int u, int l, int r, int lq, int rq) {
if(l > rq || r < lq)
return 0;
if(l >= lq && r <= rq)
return seg[u];
int mid = (l+r) >> 1;
return query(2 * u, l, mid, lq, rq) + query(2 * u + 1, mid + 1, r, lq, rq);
}
void solve() {
int n, r, q;
cin >> n >> r >> q;
vector<vector<int>> rs(r + 5), g(n + 5);
vector<int> rr(n + 5);
int rc;
cin >> rc;
rr[1] = rc;
rs[rc].push_back(1);
for(int i = 2; i <= n; i++) {
int p, cr;
cin >> p >> cr;
rr[i] = cr;
g[p].push_back(i);
rs[cr].push_back(i);
}
vector<int> s(n + 5), e(n + 5), v(n + 5), v2(n + 5);
int time = 1;
auto dfs = [&](int u, auto &dfs) -> void {
s[u] = time;
time++;
for(int &i : g[u])
dfs(i, dfs);
e[u] = time - 1;
return;
};
dfs(1, dfs);
auto dfs2 = [&](int u, int r, auto &dfs2) -> void {
v[u] += (rr[u] == r);
v2[u] = (rr[u] == r);
for(int &i : g[u]) {
v[i] = v[u];
dfs2(i, r, dfs2);
v2[u] += v2[i];
}
return;
};
map<pii, pii> mapa;
for(int i = 1; i <= r; i++) {
int sz = rs[i].size();
if(sz * sz >= n) {
v[1] = 0;
dfs2(1, i, dfs2);
for(int &j : rs[i])
update(1, 1, n, s[j], 1);
for(int j = 1; j <= r; j++) {
int ans = 0, ans2 = 0;
for(int &k : rs[j]) {
ans += v2[k];
ans2 += v[k];
}
mapa[{j, i}] = {ans, 1};
mapa[{i, j}] = {ans2, 1};
}
for(int &j : rs[i])
update(1, 1, n, s[j], 0);
}
}
while(q--) {
int r1, r2;
cin >> r1 >> r2;
if(mapa[{r1, r2}].s) {
cout << mapa[{r1, r2}].f << endl << flush;
continue;
}
for(int &j : rs[r2])
update(1, 1, n, s[j], 1);
int ans = 0;
for(int &k : rs[r1])
ans += query(1, 1, n, s[k], e[k]);
for(int &j : rs[r2])
update(1, 1, n, s[j], 0);
mapa[{r1, r2}] = ans;
cout << ans << endl << flush;
}
}
int32_t main() {
FAST;
int ct = 1;
// cin >> ct;
while(ct--)
solve();
return 0;
}