#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define sz size
const int mxN = 2e5;
const int mxR = 25*1e3;
int n,r;
vector<int> adj[mxN];
int reg[mxN];
vector<int> all[mxR];
int first[mxN];
int ssize[mxN];
vector<int> ord;
unordered_map<int,ll> cnts[mxR];
unordered_map<int,ll> rcnts[mxR];
int tarr[mxN+1];
void dfs(int node, int p){
first[node] = ord.sz();
all[reg[node]].pb(node);
ord.pb(node);
ssize[node] = 1;
for (int next : adj[node]){
if (next != p){
dfs(next,node);
ssize[node] += ssize[next];
}
}
}
int main()
{
int q;
cin >> n >> r >> q;
int a,b;
cin >> a;
reg[0] = a-1;
for (int i = 1; i < n; i++){
cin >> b >> a;
a -= 1;
b -= 1;
reg[i] = a;
adj[i].pb(b);
adj[b].pb(i);
}
dfs(0,-1);
int gsize = (double) 2 * sqrt(n);
for (int i = 0; i < r; i++){
if (all[i].sz() <= gsize){
continue;
}
memset(tarr,0,sizeof(tarr));
for (int j =0; j < all[i].sz(); j++){
tarr[first[all[i][j]]] += 1;
tarr[first[all[i][j]] + ssize[all[i][j]]] -= 1;
}
for (int j = 0; j < n; j++){
if (j > 0) tarr[j] += tarr[j-1];
cnts[i][reg[ord[j]]] += tarr[j];
}
memset(tarr,0,sizeof(tarr));
for (int j =0; j < all[i].sz(); j++){
tarr[first[all[i][j]]] += 1;
}
for (int j = 1; j < n; j++){
tarr[j] += tarr[j-1];
}
for (int j = 0; j < n; j++){
rcnts[i][reg[ord[j]]] += tarr[j+ssize[ord[j]]-1] - tarr[j];
}
}
int c,idx;
stack<int> p;
ll res;
for (int i =0; i < q; i++){
cin >> a >> b;
a -= 1;
b -= 1;
if (all[a].sz() > gsize){
cout << cnts[a][b] << '\n';
continue;
}
if (all[b].sz() > gsize){
cout << rcnts[b][a] << "\n";
continue;
}
c = 0;
idx = 0;
res = 0;
for (int j = 0; j < all[b].sz(); j++){
while (p.sz() > 0 && p.top() <= first[all[b][j]]){
p.pop();
c -= 1;
}
while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
c += 1;
p.push(first[all[a][idx]] + ssize[all[a][idx]]);
idx++;
while (p.sz() > 0 && p.top() <= first[all[b][j]]){
p.pop();
c -= 1;
}
}
res += c;
}
cout << res << '\n';
while (p.sz() > 0){
p.pop();
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:57:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
57 | if (all[i].sz() <= gsize){
| ~~~~~~~~~~~~^~~~~~~~
regions.cpp:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int j =0; j < all[i].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int j =0; j < all[i].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:90:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
90 | if (all[a].sz() > gsize){
| ~~~~~~~~~~~~^~~~~~~
regions.cpp:94:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
94 | if (all[b].sz() > gsize){
| ~~~~~~~~~~~~^~~~~~~
regions.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int j = 0; j < all[b].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:106:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
| ~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 2 |
Correct |
2 ms |
11352 KB |
Output is correct |
| 3 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 4 |
Correct |
5 ms |
11352 KB |
Output is correct |
| 5 |
Correct |
5 ms |
11352 KB |
Output is correct |
| 6 |
Correct |
11 ms |
11352 KB |
Output is correct |
| 7 |
Correct |
19 ms |
11352 KB |
Output is correct |
| 8 |
Correct |
19 ms |
11352 KB |
Output is correct |
| 9 |
Correct |
29 ms |
11864 KB |
Output is correct |
| 10 |
Correct |
51 ms |
11868 KB |
Output is correct |
| 11 |
Correct |
69 ms |
12080 KB |
Output is correct |
| 12 |
Correct |
101 ms |
12492 KB |
Output is correct |
| 13 |
Correct |
115 ms |
12408 KB |
Output is correct |
| 14 |
Correct |
156 ms |
12536 KB |
Output is correct |
| 15 |
Correct |
188 ms |
15404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
747 ms |
15684 KB |
Output is correct |
| 2 |
Correct |
757 ms |
15132 KB |
Output is correct |
| 3 |
Correct |
1320 ms |
17472 KB |
Output is correct |
| 4 |
Correct |
173 ms |
12676 KB |
Output is correct |
| 5 |
Correct |
256 ms |
14532 KB |
Output is correct |
| 6 |
Correct |
523 ms |
46992 KB |
Output is correct |
| 7 |
Correct |
913 ms |
14968 KB |
Output is correct |
| 8 |
Correct |
860 ms |
19684 KB |
Output is correct |
| 9 |
Correct |
1458 ms |
19204 KB |
Output is correct |
| 10 |
Correct |
2213 ms |
24380 KB |
Output is correct |
| 11 |
Correct |
2346 ms |
20492 KB |
Output is correct |
| 12 |
Correct |
899 ms |
21932 KB |
Output is correct |
| 13 |
Correct |
1160 ms |
23052 KB |
Output is correct |
| 14 |
Correct |
1561 ms |
41216 KB |
Output is correct |
| 15 |
Correct |
1978 ms |
29136 KB |
Output is correct |
| 16 |
Correct |
1889 ms |
36320 KB |
Output is correct |
| 17 |
Correct |
1869 ms |
52700 KB |
Output is correct |
