#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()
{
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
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;
}
// cnts[i].resize(n);
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];
}
// rcnts[i].resize(n);
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];
}
}
/*cout << gsize<< " gsize\n";
for (int i =0; i < r; i++){
cout << all[i].sz() << ":\n";
for (int j = 0; j < all[i].sz(); j++) cout << all[i][j] << " ";
cout << '\n';
if (all[i].sz() <= gsize){
continue;
}
for (int j =0; j < n; j++){
cout << cnts[i][j] << " ";
}
cout << '\n';
for (int j = 0; j < n; j++) cout << rcnts[i][j] << " ";
cout << '\n';
}
*/
int c,idx;
stack<int> p;
ll res;
/* for (int i =0; i <r; i++){
cout << i << ": ";
for (int j : all[i]){
cout << first[j] << "-" << ssize[j] << " ";
}
cout << '\n';
}*/
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;
// cout << a << "," << b << ": ";
for (int j = 0; j < all[b].sz(); j++){
// cout << p.sz() << " " << idx << " " << all[a].sz() << '\n';
while (p.sz() > 0 && p.top() <= first[all[b][j]]){
p.pop();
// cout << "Rm\n";
c -= 1;
}
// cout << ";\n";
while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
c += 1;
// cout << all[a][idx] << '\n';
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;
}
}
// cout << p.sz() << "l\n";
// cout << c << ' ' << p.top() << '\n';
// cout << c << '\n';
res += c;
}
cout << res << '\n';
while (p.sz() > 0){
p.pop();
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:59:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | if (all[i].sz() <= gsize){
| ~~~~~~~~~~~~^~~~~~~~
regions.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int j =0; j < all[i].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int j =0; j < all[i].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:114:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | if (all[a].sz() > gsize){
| ~~~~~~~~~~~~^~~~~~~
regions.cpp:118:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
118 | if (all[b].sz() > gsize){
| ~~~~~~~~~~~~^~~~~~~
regions.cpp:126:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int j = 0; j < all[b].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:134:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
| ~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11352 KB |
Output is correct |
| 2 |
Correct |
2 ms |
11352 KB |
Output is correct |
| 3 |
Correct |
3 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 |
17 ms |
11352 KB |
Output is correct |
| 8 |
Correct |
23 ms |
11352 KB |
Output is correct |
| 9 |
Correct |
29 ms |
11864 KB |
Output is correct |
| 10 |
Correct |
44 ms |
12020 KB |
Output is correct |
| 11 |
Correct |
72 ms |
12068 KB |
Output is correct |
| 12 |
Correct |
89 ms |
12452 KB |
Output is correct |
| 13 |
Correct |
103 ms |
12288 KB |
Output is correct |
| 14 |
Correct |
164 ms |
12520 KB |
Output is correct |
| 15 |
Correct |
196 ms |
15548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
818 ms |
15592 KB |
Output is correct |
| 2 |
Correct |
749 ms |
15172 KB |
Output is correct |
| 3 |
Correct |
1393 ms |
17524 KB |
Output is correct |
| 4 |
Correct |
195 ms |
12700 KB |
Output is correct |
| 5 |
Correct |
237 ms |
14460 KB |
Output is correct |
| 6 |
Correct |
464 ms |
46740 KB |
Output is correct |
| 7 |
Correct |
889 ms |
14992 KB |
Output is correct |
| 8 |
Correct |
919 ms |
19748 KB |
Output is correct |
| 9 |
Correct |
1455 ms |
19212 KB |
Output is correct |
| 10 |
Correct |
2311 ms |
24372 KB |
Output is correct |
| 11 |
Correct |
2338 ms |
20440 KB |
Output is correct |
| 12 |
Correct |
834 ms |
21892 KB |
Output is correct |
| 13 |
Correct |
1188 ms |
23108 KB |
Output is correct |
| 14 |
Correct |
1446 ms |
41212 KB |
Output is correct |
| 15 |
Correct |
1929 ms |
28808 KB |
Output is correct |
| 16 |
Correct |
1894 ms |
36252 KB |
Output is correct |
| 17 |
Correct |
2001 ms |
53004 KB |
Output is correct |
