【CodeForces 208E】Blood Cousins
题意:给你一个森林,m个询问:v,p
求有多少个点(除v外) 与 v的第p个祖先相同
这个题首先要解决找某个点的第p个祖先的问题,可以采用倍增法
记录一个二维数组p[u][i]表示u的第2^i个祖先,那么通过这个数组我们就可以知道u的上面任意深度(相对于u)祖先是谁(巧妙的利用二进制)
具体求法和用法见下,还可以找LCA的
const int POW = 18;
void dfs(int u,int fa){
d[u]=d[fa]+1;
p[u][0]=fa;
for(int i=1;i<POW;i++) p[u][i]=p[p[u][i-1]][i-1];
int sz=edge[u].si