代码:
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;bool f=false;char ch=getchar();
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
#define PII pair<int,int>
const int N=2e5+5,M=25005;
int head[N],nex[N],a[N],Ans[N];
vector<PII> v1[M],v2[M];
inline void Add(int u,int v){nex[v]=head[u],head[u]=v;}
int sum1[N],sum2[N];
void DFS(int x){
for(int i=0,l=v2[a[x]].size();i<l;i++) Ans[v2[a[x]][i].second]+=sum2[v2[a[x]][i].first];
sum1[a[x]]++,sum2[a[x]]++;
for(int i=0,l=v1[a[x]].size();i<l;i++) Ans[v1[a[x]][i].second]-=sum1[v1[a[x]][i].first];
for(int v=head[x];v;v=nex[v]) DFS(v);
for(int i=0,l=v1[a[x]].size();i<l;i++) Ans[v1[a[x]][i].second]+=sum1[v1[a[x]][i].first];
sum2[a[x]]--;
return ;
}
map<PII,int>f;
int n,R,Q,siz,pos[N],cnt[M];
int main(){
read(n),read(R),read(Q),siz=sqrt(n);
read(a[1]),cnt[a[1]]++;
for(int i=2,x,y;i<=n;i++) read(x),read(y),Add(x,i),a[i]=y,cnt[y]++;
for(int i=1,r1,r2;i<=Q;i++){
map<PII,int>::iterator it;
read(r1),read(r2);
if((it=f.find(make_pair(r1,r2)))==f.end()){
f[make_pair(r1,r2)]=pos[i]=i;
if(cnt[r2]<=siz) v2[r2].push_back(make_pair(r1,i));
else v1[r1].push_back(make_pair(r2,i));
}
else pos[i]=it->second;
}
DFS(1);
for(int i=1;i<=Q;i++) write(Ans[pos[i]]),putchar('
');
return 0;
}
注意
这道题值得学习的是对于每个点求祖先贡献的那一步。