LCA的思想，也就是倍增法，时间复杂度O(Q*logN)

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 100010

#define maxq 100010

int q,n;

int fa[maxn][20];

int dep[maxn];//每个点的深度，根节点的深度为1

int lg2[maxn];//lg2[i]就是log2(i)向下取整

vector<int> tu[maxn];

void dfs(int root,int father){

    fa[root][0]=father;

    dep[root]=dep[father]+1;

    for(int i=1;i<=lg2[dep[root]];i++){

        fa[root][i]=fa[fa[root][i-1]][i-1];

    }

    for(auto v:tu[root]){

        dfs(v,root);

    }

}

bool check(int x,int y){

    while(dep[y]>dep[x]){

        y=fa[y][lg2[dep[y]-dep[x]]];

    }

    if(x==y)return 1;

    return 0;

}

int main(){

    scanf("%d%d",&n,&q);

    int u,v;

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

        scanf("%d%d",&u,&v);

        tu[u].push_back(v);

    }

    lg2[0]=-999999;

    lg2[1]=0;

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

        lg2[i]=lg2[i-1]+(1<<(lg2[i-1]+1)==i);

    }

    dfs(1,0);

    int x,y;

    while(q--){

        scanf("%d%d",&x,&y);

        if(check(x,y))printf("YES\n");

        else printf("NO\n");

    }

    system("pause");

    return 0;

}