#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;
ll heavy_ans[B][rax][2];
int idx[rax];
map<pair<int,int>,ll> 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) {
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; }
ll 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 |
2 ms |
13912 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13912 KB |
Output is correct |
| 3 |
Correct |
4 ms |
14196 KB |
Output is correct |
| 4 |
Correct |
4 ms |
14208 KB |
Output is correct |
| 5 |
Correct |
7 ms |
13964 KB |
Output is correct |
| 6 |
Correct |
11 ms |
15060 KB |
Output is correct |
| 7 |
Correct |
22 ms |
14368 KB |
Output is correct |
| 8 |
Correct |
28 ms |
15372 KB |
Output is correct |
| 9 |
Correct |
49 ms |
15280 KB |
Output is correct |
| 10 |
Correct |
109 ms |
15724 KB |
Output is correct |
| 11 |
Correct |
207 ms |
16028 KB |
Output is correct |
| 12 |
Correct |
244 ms |
16212 KB |
Output is correct |
| 13 |
Correct |
386 ms |
17044 KB |
Output is correct |
| 14 |
Correct |
705 ms |
16800 KB |
Output is correct |
| 15 |
Correct |
784 ms |
19700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
92 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
91 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
98 ms |
131072 KB |
Execution killed with signal 9 |
| 4 |
Correct |
685 ms |
18176 KB |
Output is correct |
| 5 |
Correct |
620 ms |
19132 KB |
Output is correct |
| 6 |
Runtime error |
82 ms |
131072 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
91 ms |
131072 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
95 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Execution timed out |
8021 ms |
30316 KB |
Time limit exceeded |
| 10 |
Runtime error |
122 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Execution timed out |
8034 ms |
30928 KB |
Time limit exceeded |
| 12 |
Runtime error |
156 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
140 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
157 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
149 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
148 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
162 ms |
131072 KB |
Execution killed with signal 9 |
