#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
const int nax = 2e5, B = 450, rax = 25000;
int n;
vector<int> adj[nax];
vector<int> nodes[rax];
int tin[nax],tout[nax],color[nax],timer=0;
int heavy_ans[B][rax][2];
int idx[rax];
map<pair<int,int>,int> computed;
struct query1 {
int st[4*nax];
void upd(int p,int nw,int u=1,int tl=0,int tr=n-1) {
if (tl == tr) {
st[u] = nw;
return;
}
int mid = (tl+tr)/2;
if (p <= mid) {
upd(p,nw,2*u,tl,mid);
} else {
upd(p,nw,2*u+1,mid+1,tr);
}
st[u] = st[2*u] + st[2*u+1];
}
int qry(int l,int r,int u=1,int tl=0,int tr=n-1) {
if (l > r) {
return 0;
}
if (l == tl && r == tr) {
return st[u];
}
int mid = (tl+tr)/2;
return qry(l,min(r,mid),2*u,tl,mid)+qry(max(mid+1,l),r,2*u+1,mid+1,tr);
}
} st1;
struct query2 {
int st[4*nax];
void add(int l,int r,int k,int u=1,int tl=0,int tr=n-1) {
if (l > r) {
return;
}
if (l == tl && r == tr) {
st[u] += k;
return;
}
int mid = (tl+tr)/2;
add(l,min(r,mid),2*u,tl,mid);
add(max(mid+1,l),r,2*u+1,mid+1,tr);
}
int qry(int p,int u=1,int tl=0,int tr=n-1) {
if (tl == tr) {
return st[u];
}
int mid = (tl+tr)/2;
if (p <= mid) {
return st[u] + qry(p,2*u,tl,mid);
} else {
return st[u] + qry(p,2*u+1,mid+1,tr);
}
}
} st2;
void dfs(int u=0,int e=-1) {
tin[u] = timer++;
for (int &v: adj[u]) if (v != e) {
dfs(v,u);
}
tout[u] = timer-1;
}
void solve() {
int r,q;
cin >> n >> r >> q;
cin >> color[0];
for (int i=1,p;i<n;i++) {
cin >> p >> color[i];
--p;
adj[p].push_back(i);
adj[i].push_back(p);
}
for (int i=0;i<n;i++) {
color[i]--;
}
dfs();
for (int i=0;i<n;i++) {
nodes[color[i]].push_back(i);
}
int sz = 0;
for (int i=0;i<r;i++) {
idx[i] = -1;
if ((int) nodes[i].size() >= B) {
assert(sz < B);
idx[i] = sz;
// lui e' il figlio
for (int &u: nodes[i]) {
st1.upd(tin[u],1);
}
for (int j=0;j<n;j++) {
if (color[j] == i) { continue; }
heavy_ans[sz][color[j]][0] += st1.qry(tin[j],tout[j]);
}
for (int &u: nodes[i]) {
st1.upd(tin[u],0);
}
// lui e' il padre
for (int &u: nodes[i]) {
st2.add(tin[u],tout[u],1);
}
for (int j=0;j<n;j++) {
if (color[j] == i) { continue; }
heavy_ans[sz][color[j]][1] += st2.qry(tin[j]);
}
for (int &u: nodes[i]) {
st2.add(tin[u],tout[u],-1);
}
sz++;
}
}
for (int a,b;q--;) {
cin >> a >> b;
--a,--b;
auto c = make_pair(a,b);
if (computed.count(c)) { cout << computed[c] << endl; continue; }
int ans = 0;
if (idx[a] != -1) {
// a is heavy
ans = heavy_ans[idx[a]][b][1];
} else if (idx[b] != -1) {
// b is heavy
ans = heavy_ans[idx[b]][a][0];
} else {
for (auto &x: nodes[b]) {
st1.upd(tin[x],1);
}
for (auto &x: nodes[a]) {
ans += st1.qry(tin[x],tout[x]);
}
for (auto &x: nodes[b]) {
st1.upd(tin[x],0);
}
}
computed[c] = ans;
cout << ans << endl;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int _t = 1;
for (int i=1;i<=_t;i++) {
solve();
}
}
// Dato un albero in cui ogni nodo ha un tag, query online che chiedono il numero di coppie di nodi con tag E1 ed E2, tali che
// E1 e' un antenato di E2.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13912 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13912 KB |
Output is correct |
| 3 |
Correct |
4 ms |
14124 KB |
Output is correct |
| 4 |
Correct |
5 ms |
14124 KB |
Output is correct |
| 5 |
Correct |
7 ms |
15164 KB |
Output is correct |
| 6 |
Correct |
12 ms |
15032 KB |
Output is correct |
| 7 |
Correct |
22 ms |
15068 KB |
Output is correct |
| 8 |
Correct |
26 ms |
14488 KB |
Output is correct |
| 9 |
Correct |
42 ms |
15412 KB |
Output is correct |
| 10 |
Correct |
104 ms |
15800 KB |
Output is correct |
| 11 |
Correct |
207 ms |
15908 KB |
Output is correct |
| 12 |
Correct |
252 ms |
17184 KB |
Output is correct |
| 13 |
Correct |
359 ms |
17156 KB |
Output is correct |
| 14 |
Correct |
694 ms |
17012 KB |
Output is correct |
| 15 |
Correct |
801 ms |
19868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
95 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
98 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
95 ms |
131072 KB |
Execution killed with signal 9 |
| 4 |
Correct |
658 ms |
18020 KB |
Output is correct |
| 5 |
Correct |
627 ms |
19652 KB |
Output is correct |
| 6 |
Runtime error |
87 ms |
131072 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
90 ms |
131072 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
101 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Execution timed out |
8080 ms |
30932 KB |
Time limit exceeded |
| 10 |
Runtime error |
132 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Execution timed out |
8045 ms |
31188 KB |
Time limit exceeded |
| 12 |
Runtime error |
150 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
147 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
156 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
137 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
146 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
155 ms |
131072 KB |
Execution killed with signal 9 |
