#include <bits/stdc++.h>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 5;
const int M = 2.5e4 + 5;
const int B = 450;
int n, re, q, init;
struct node {
int d, l, r;
node(int d, int l, int r) : d(d), l(l), r(r) {}
};
vector<node> vec;
int newleaf(int d) {
vec.emplace_back(d, -1, -1);
return (int)vec.size() - 1;
}
int newpar(int l, int r) {
vec.emplace_back(0, l, r);
return (int)vec.size() - 1;
}
int build(int l = 1, int r = re) {
if(l == r) return newleaf(0);
int mid = (l + r) >> 1;
return newpar(build(l, mid), build(mid + 1, r));
}
int update(int x, int k, int p, int l = 1, int r = re) {
if(l == r) return newleaf(vec[p].d + k);
int mid = (l + r) >> 1;
if(x <= mid) return newpar(update(x, k, vec[p].l, l, mid), vec[p].r);
else return newpar(vec[p].l, update(x, k, vec[p].r, mid + 1, r));
}
int get_val(int x, int p, int l = 1, int r = re) {
if(l == r) return vec[p].d;
int mid = (l + r) >> 1;
if(x <= mid) return get_val(x, vec[p].l, l, mid);
else return get_val(x, vec[p].r, mid + 1, r);
}
int R[N], ver[N], hv[N];
int id[M], inv[M], ptr;
long sum[B][B];
vector<int> g[N], emp[M];
int preprocess(int u) {
int sz = 1; pii ret(0, -1);
for(int v : g[u]) {
int z = preprocess(v);
sz += z, ret = max(ret, pii(z, v));
}
hv[u] = ret.y;
return sz;
}
void sack(int u, vector<int> &sub) {
if(hv[u] != -1) sack(hv[u], sub), ver[u] = ver[hv[u]];
vector<int> now;
for(int v : g[u]) if(v != hv[u]) {
sack(v, now);
for(int x : now) {
sub.emplace_back(x);
ver[u] = update(R[x], 1, ver[u]);
}
now = vector<int>();
}
sub.emplace_back(u), ver[u] = update(R[u], 1, ver[u]);
if(id[R[u]]) for(int i = 1; i <= ptr; i++)
sum[id[R[u]]][i] += get_val(inv[i], ver[u]);
}
int main() {
scanf("%d %d %d %d", &n, &re, &q, R + 1);
emp[R[1]].emplace_back(1);
for(int i = 2, p; i <= n; i++) {
scanf("%d %d", &p, R + i);
g[p].emplace_back(i);
emp[R[i]].emplace_back(i);
}
for(int i = 1; i <= re; i++) if((int)emp[i].size() >= B)
inv[id[i] = ++ptr] = i;
init = build();
fill_n(ver, N, init);
vector<int> tmp;
preprocess(1), sack(1, tmp);
for(int i = 1, a, b; i <= q; i++) {
scanf("%d %d", &a, &b);
// if(id[a] && id[b]) printf("%lld\n", sum[id[a]][id[b]]);
// else {
long ans;
// if(!id[a]) {
ans = 0;
for(int u : emp[a]) ans += get_val(b, ver[u]);
// } else {
// ans = (long)emp[a].size() * (long)emp[b].size();
// for(int u : emp[b]) ans -= get_val(a, ver[u]);
// }
printf("%lld\n", ans);
}
fflush(stdout);
}
return 0;
}
Compilation message
regions.cpp:117:5: error: expected unqualified-id before 'return'
117 | return 0;
| ^~~~~~
regions.cpp:118:1: error: expected declaration before '}' token
118 | }
| ^
regions.cpp: In function 'int main()':
regions.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
85 | scanf("%d %d %d %d", &n, &re, &q, R + 1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
88 | scanf("%d %d", &p, R + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
101 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
