蓝桥杯2018年第九届真题-版本分支(倍增)

解题思路:
常规的求祖先方法往往一次向上移动1，采用倍增的方法一次向上移动2^k,nlogn处理出倍增数组，logn查询。
注意事项:
提一个题解区没说的，不要用cin读，会超时。
参考代码:

#include<bits/stdc++.h>
using namespace std;
#define maxx 130000
#define int long long
int n,q,a,b;
int fa[maxx];
int faaa[maxx][22];
vector<int> G[maxx];
int dep[maxx];
void starting()
{
  for(int i=1;i<=n;++i)
   faaa[i][0]=fa[i];

 for(int j=1;j<=20;++j) //循环位置
  for(int i=1;i<=n;++i)
    faaa[i][j]=faaa[faaa[i][j-1]][j-1];
}
void dfs(int i)
{
   for(int j=0;j<G[i].size();++j)
   {dep[G[i][j]]=dep[i]+1;
    dfs(G[i][j]);}

}
int cal(int x,int y)
{
  if(dep[x]>dep[y]) return 0;
  int cha=dep[y]-dep[x];
  for(int i=0;i<20;++i)
  {
    if(cha%2==1) y=faaa[y][i];
    cha/=2;
  }
  if(y==x) return 1;
  else return 0;
}
signed main()
{
  scanf("%d %d",&n,&q);
  for(int i=1;i<n;++i)
 {scanf("%d %d",&a,&b);
 fa[b]=a;
 G[a].push_back(b);
 }
 for(int i=1;i<=n;++i)
  if(fa[i]==0) dfs(i);
  starting();
 for(int i=1;i<=q;++i)
 {
  scanf("%d %d",&a,&b);
  if(cal(a,b)) cout<<"YES\n";
  else cout<<"NO\n";
 }
 

}