倍增维护父节点

解题思路: 这和经典算法倍增求最近公共祖先是一样的思路，可以去学习下最近公共祖先怎么求，就能做出这道题了。

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn = 5e5 + 10;

int lg[maxn], fa[maxn][30], dep[maxn];

struct edge{

    int to, nxt;

}g[maxn<<1];

int head[maxn] ,tot = 1;

void addedge(int u, int v)

{

    g[++tot] = {v, head[u]}; head[u] = tot;

}

void dfs(int u, int f)

{

    fa[u][0] = f;

    dep[u] = dep[f] + 1;

    for(int i = 1; i <= lg[dep[u]]; ++i){

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

    }

    for(int i = head[u]; i ; i = g[i].nxt){

        if(g[i].to != f) dfs(g[i].to, u);

    }

}

bool lca(int x, int y)

{

    while(dep[x] < dep[y]) y = fa[y][lg[dep[y] - dep[x]]];

    return x == y;

}

int n, m, s, a, b;

int main()

{

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

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

        scanf("%d%d", &a, &b);

        addedge(a, b);

        addedge(b, a);

    }

    lg[0] = -1;

    for(int i = 1; i <= n; ++i) lg[i] = lg[i>>1] + 1;

    dfs(1, 0);

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

        scanf("%d%d", &a, &b);

        if(dep[a] > dep[b]) printf("NO\n");

        else{

            if(a == b) printf("YES\n");

            else if(lca(a, b)) printf("YES\n");

            else printf("NO\n");

        }

    }

    return 0;

}