This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize ("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef priority_queue<int> pq;
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;}
#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define carp(x,y,mod) (((x)%mod)*((y)%mod))%mod
#define topla(x,y,mod) (((x)%mod)+((y)%mod))%mod
#define mid (l+r)/2
//#define endl '\n'
const int MAXN=2e5+3;
int n,q,r;
vi adj[MAXN];
vi euler;
int sub[MAXN],ind[MAXN],dep[MAXN];
int p[MAXN];
vi t[4*MAXN];
vi reg[MAXN];
int home[MAXN];
void dfs(int nd,int ata,int h){
dep[nd]=h;
sub[nd]=1;
euler.pb(nd);
for(auto kom:adj[nd]){
if(kom!=ata){
dfs(kom,nd,h+1);
sub[nd]+=sub[kom];
}
}
}
void merge(vi& c,vi& a,vi& b){
int sz1=a.size();
int sz2=b.size();
int p1,p2;
p1=p2=0;
while(p1<sz1 or p2<sz2){
if(p2>=sz2 or (p1<sz1 and a[p1]<=b[p2])){
c.pb(a[p1++]);
}
else c.pb(b[p2++]);
}
}
void build(int nd=1,int l=1,int r=n){
if(l==r){
t[nd].pb(home[euler[l]]);
return;
}
build(nd*2,l,mid);
build(nd*2+1,mid+1,r);
merge(t[nd],t[nd*2],t[nd*2+1]);
}
int query(int ql,int qr,int vv,int nd=1,int l=1,int r=n){
if(l>r or l>qr or r<ql) return 0;
if(ql<=l and r<=qr){
auto bir=lower_bound(all(t[nd]),vv);
auto iki=upper_bound(all(t[nd]),vv);
return iki-bir;
}
auto s1=query(ql,qr,vv,nd*2,l,mid);
auto s2=query(ql,qr,vv,nd*2+1,mid+1,r);
return s1+s2;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
euler.pb(0);
cin>>n>>r>>q;
cin>>home[1];
reg[home[1]].pb(1);
FORE(i,2,n+1){
cin>>p[i]>>home[i];
reg[home[i]].pb(i);
adj[p[i]].pb(i);
adj[i].pb(p[i]);
}
dfs(1,0,0);
FORE(i,1,n+1){
ind[euler[i]]=i;
}
build();
while(q--){
int a,b;
cin>>a>>b;
int cev=0;
for(auto el:reg[a]){
cev+=query(ind[el],ind[el]+sub[el]-1,b);
}
cout<<cev<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |