5086 C

https://ac.nowcoder.com/acm/contest/5086/C

LCA

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

vector<int>p2[100'010];
int d[100'010];
int f[100'010][32];

int n,q;

void dfs(int i,int fa,int dep=0){
  f[i][0] = fa;
  d[i] = dep;
  for(auto item : p2[i]){
    if(fa == item)continue;
    dfs(item,i,dep+1);
  }
}

int r(int i,int j){
  if(d[i] > d[j])swap(i,j);
  per(off,0,20){
    if(d[j]-d[i] >= (1<<off) ){
      j=f[j][off];
    }
  }
  if(i == j)return i;
  per(off,0,20){
    if(f[i][off] != f[j][off]){
      i=f[i][off];
      j=f[j][off];
    }
  }
  return f[i][0];
}

void work(){
  scanf("%d %d",&n,&q);
  rep(i,1,n+1){
    p2[i].clear();
  }
  rep(i,0,n-1){
    int x,y;
    scanf("%d %d",&x,&y);
    p2[x].pb(y);
    p2[y].pb(x);
  }
  dfs(1,1);
  rep(off,1,20){
    rep(i,1,n+1){
      f[i][off]=f[f[i][off-1]][off-1];
    }
  }

  while(q--){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    int rbc = r(b,c);
    int step = d[b]-d[rbc]+d[c]-d[rbc];
    if(d[a] < d[c] + step){
      printf("YES\n");
      continue;
    }else if(d[a] > d[c]+step){
      printf("NO\n");
      continue;
    }

    int rac = r(a,c);
    if(rac != 1){
      printf("YES\n");
    }else{
      printf("NO\n");
    }
  }
}

int main(){
  int t;
  cin>>t;
  while(t--){
    work();
  }

  return 0;
}