https://www.cnblogs.com/cutemush/p/12797280.html
给定一棵有根树，每次询问所有颜色为a的节点的子树中颜色为b的节点个数之和。
思路：
考虑将询问按b的出现次数分类。
若b<=sqrt(n)，我们可以在每个b节点用一个vector记录它涉及到的询问。
dfs，用桶记录从根节点到这个节点每种颜色的出现次数，就可以更新答案了。
由于总点数为O(q*sqrt(n))，时间复杂度为O(q*sqrt(n))
若b>sqrt(n)，那么只有不超过sqrt(n)种这样的颜色，我们可以在每个a节点用一个vector记录它涉及到的询问。
dfs，用桶记录子树中各颜色出现次数，更新答案。时间复杂度为O(n*sqrt(n))
所以总时间复杂度为O(q*sqrt(n)+n*sqrt(n))
具体看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if(p1==p2){
p2=(p1=buf)+fread(buf,1,100000,stdin);
if(p1==p2)return EOF;
}
return *p1++;
}
inline void Read(int& x){
char c=nc();
for(;c<'0'||c>'9';c=nc());
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
}
#define N 200010
#define R 25010
#define ll long long
struct Node
{
int x,y;
Node(){}
Node(int x,int y):x(x),y(y){}
bool operator<(Node a)const
{
return x<a.x||(x==a.x&&y<a.y);
}
}b[N];
map<Node,int>M;
vector<int>g[N],B[N],A[N];
int n,r,q,f[N],a[N],S,Tmp[R],Sum[R],i,F[N];
ll Ans[N];
inline void Dfs1(int x)
{
Tmp[a[x]]++;
for(int i=0;i<B[a[x]].size();i++)
Ans[B[a[x]][i]]+=Tmp[b[B[a[x]][i]].x];
for(int i=0;i<g[x].size();i++)
Dfs1(g[x][i]);
Tmp[a[x]]--;
}
inline void Dfs2(int x)
{
for(int i=0;i<A[a[x]].size();i++)
Ans[A[a[x]][i]]-=Tmp[b[A[a[x]][i]].y];
Tmp[a[x]]++;
for(int i=0;i<g[x].size();i++)
Dfs2(g[x][i]);
for(int i=0;i<A[a[x]].size();i++)
Ans[A[a[x]][i]]+=Tmp[b[A[a[x]][i]].y];
}
char s[30];
int Len;
inline void Print(ll x){
if(x==0)putchar(48);
for(Len=0;x;x/=10)s[++Len]=x%10;
for(;Len;)putchar(s[Len--]+48);
putchar('
');
}
int main()
{
Read(n);Read(r);Read(q);
S=(int)sqrt((double)n)+1;
Read(a[1]);
Sum[a[1]]++;
for(i=2;i<=n;i++)
Read(f[i]),
g[f[i]].push_back(i),
Read(a[i]),
Sum[a[i]]++;
for(i=1;i<=q;i++)
{
Read(b[i].x);
Read(b[i].y);
F[i]=i;
if(M.count(Node(b[i].x,b[i].y)))
F[i]=M[Node(b[i].x,b[i].y)];
else
{
M[Node(b[i].x,b[i].y)]=i;
if (Sum[b[i].y]<=S)
//若b<=sqrt(n)，我们可以在每个b节点用一个vector记录它涉及到的询问。
//dfs，用桶记录从根节点到这个节点每种颜色的出现次数，就可以更新答案了。
B[b[i].y].push_back(i);
else
//若b>sqrt(n)，那么只有不超过sqrt(n)种这样的颜色，
//我们可以在每个a节点用一个vector记录它涉及到的询问。
//dfs，用桶记录子树中各颜色出现次数，更新答案。时间复杂度为O(n*sqrt(n))
A[b[i].x].push_back(i);
}
}
Dfs1(1);
Dfs2(1);
for(i=1;i<=q;i++)
Print(Ans[F[i]]);
return 0;
}