codeforces208E Blood Cousins

题目链接：codeforces208E

正解：$dsu$ $on$ $tree$

解题报告：

　　又是一波$dsu$ $on$ $tree$咯…

　　$p$级$cousin$其实就是对于$x$的$p$级祖先统计一下和$x$深度相同的点的个数，链剖$+dsu$ $on$ $tree$就好咯。

//It is made by ljh2000

//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <set>

#include <string>

#include <complex>

#include <bitset>

using namespace std;

typedef long long LL;

typedef long double LB;

typedef complex<double> C;

const double pi = acos(-1);

const int MAXN = 100011;

const int MAXM = 200011;

int n,m,ecnt,first[MAXN],to[MAXM],next[MAXM],size[MAXN],son[MAXN];

int f[MAXN][18],father[MAXN],deep[MAXN],ans[MAXN],Son,cnt[MAXN];

struct node{ int id,h; }tmp;

vector<node>w[MAXN];

inline void link(int x,int y){ next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; }

inline int find(int x){ if(father[x]!=x) father[x]=find(father[x]); return father[x]; }

inline void merge(int x,int y){ x=find(x); y=find(y); if(x!=y) father[y]=x; }

inline int getint(){

    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();

    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;

}

inline void dfs(int x,int fa){

	size[x]=1;

	for(int i=first[x];i;i=next[i]) {

		int v=to[i]; if(v==fa) continue;

		f[v][0]=x; deep[v]=deep[x]+1;

		dfs(v,x); size[x]+=size[v];

		if(size[v]>size[son[x]]) son[x]=v;

	}

}

inline int lca(int x,int t){

	for(int i=17;i>=0;i--)

		if(t&(1<<i))

			x=f[x][i],t^=(1<<i);

	return x;

}

inline void add(int x,int fa,int val){

	cnt[deep[x]]+=val;

	for(int i=first[x];i;i=next[i]) {

		int v=to[i]; if(v==fa || v==Son) continue;

		add(v,x,val);

	}

}

inline void solve(int x,int fa,bool top){

	for(int i=first[x];i;i=next[i]) {

		int v=to[i]; if(v==son[x] || v==fa) continue;

		solve(v,x,1);

	}

	if(son[x])

		solve(son[x],x,0),Son=son[x];

	add(x,fa,1); Son=0;

	for(int i=0,ss=w[x].size();i<ss;i++) {

		tmp=w[x][i];

		ans[tmp.id]=cnt[tmp.h]-1;

	}

	if(top)

		add(x,fa,-1);

}

inline void work(){

	n=getint(); for(int i=1;i<=n;i++) father[i]=i; int x,y;

	for(int i=1;i<=n;i++) {

		x=getint(); f[i][0]=x;

		if(x!=0) link(x,i);

		merge(x,i);

	}

	for(int i=1;i<=n;i++)

		if(f[i][0]==0)

			dfs(i,0);

	for(int j=1;j<=17;j++)

		for(int i=1;i<=n;i++)

			f[i][j]=f[f[i][j-1]][j-1];

	m=getint();

	for(int i=1;i<=m;i++) {

		x=getint(); y=getint();

		if(deep[x]<y)  { ans[i]=0; continue; }

		tmp.h=deep[x]; x=lca(x,y); if(x==0) { ans[i]=0; continue; }

		tmp.id=i; w[x].push_back(tmp);

	}

	for(int i=1;i<=n;i++)

		if(f[i][0]==0)

			solve(i,0,1);

	for(int i=1;i<=m;i++) printf("%d ",ans[i]);

}

int main()

{

    work();

    return 0;

}

//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。