记录编号	451944	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[IOI 2009]区域发展	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	8.970 s
提交时间	2017-09-18 17:41:30	内存使用	106.20 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int N=2e5+10,M=25010;
int n,m,q,c[N],w[N],head[N],next[N];
void add(int f,int t){
    static int cnt=0;
    w[++cnt]=t;
    next[cnt]=head[f];
    head[f]=cnt;
}
int size[M],ans1[510][M],ans2[510][M];
int id[M],ID,*ans,flag;
vector<int> L[N],R[N];
void dfs(int x){
    size[c[x]]++;
    static int cnt=0;
    L[c[x]].push_back(++cnt);
    for (int i=head[x];i;i=next[i]) dfs(w[i]);
    R[c[x]].push_back(cnt);
}
int query(int x,int y){
    int pp=0,pl=0,pr=0,ans=0,cnt=0;
    while (pp<size[y]||pl<size[x]||pr<size[x]){
        int vp=L[y][pp],vl=L[x][pl],vr=R[x][pr];
        if (vl<=vp&&vl<=vr) ans-=cnt,pl++;else
        if (vp<vl&&vp<=vr) cnt++,pp++;else
        if (vr<vl&&vr<vp) ans+=cnt,pr++;
    }
    return ans;
}
void dfs1(int x){//求r1=x的答案
    static int cnt=0;
    if (c[x]==flag) cnt++;else ans[c[x]]+=cnt;
    for (int i=head[x];i;i=next[i]) dfs1(w[i]);
    if (c[x]==flag) cnt--;
}
int cnt[N];
void dfs2(int x){//求r2=x的答案
    cnt[x]=0;
    for (int i=head[x];i;i=next[i]) dfs2(w[i]),cnt[x]+=cnt[w[i]];
    if (c[x]==flag) cnt[x]++;else ans[c[x]]+=cnt[x];
}
int main()
{
    freopen("region.in","r",stdin);
    freopen("region.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&q,&c[1]);
    for (int i=2;i<=n;i++){
        int x;
        scanf("%d%d",&x,&c[i]);
        add(x,i);
    }
    dfs(1);
    for (int i=1;i<=m;i++){
        L[i].push_back(1e9);
        R[i].push_back(1e9);
    }
    int block_size=sqrt(n);
    for (int i=1;i<=m;i++)
    if (size[i]>block_size){
        id[i]=++ID;flag=i;
        ans=ans1[ID];dfs1(1);
        ans=ans2[ID];dfs2(1);
    }
    while (q--){
        int x,y,ans=0;
        scanf("%d%d",&x,&y);
        if (size[x]>block_size) ans=ans1[id[x]][y];else
        if (size[y]>block_size) ans=ans2[id[y]][x];else
            ans=query(x,y);
        printf("%d\n",ans);
    }
    return 0;
}