【题意】给了一颗V<=100000的有向的，但是忽略方向的一颗树，每次查询(u,v)是否可以到达？

【解题方法】随便一个点当成根，那么边有两种，一种是向上一种向下。我们可以预处理dp[u]表示u向上或者下的边的条数，有了这个就可以快速算出u向上或者向下的边的条数。当询问(u,v)是否可以到达的时候，只需要判断u->lca(u,v)lca(u,v)->v路径上的上下边是否相同就可以了。

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int n,q;
struct edge{int v;bool flag;};
vector<edge>G[maxn];
int dep[maxn],dp[maxn],p[18][maxn];
void dfs(int u,int f,int d){
    dep[u]=d;p[0][u]=f;
    for(int i=0; i<G[u].size(); i++){
        edge e=G[u][i];
        if(e.v==f) continue;
        dp[e.v]=dp[u]+(e.flag?1:-1);
        dfs(e.v,u,d+1);
    }
}
void build()
{
    dp[1]=0;
    dfs(1,-1,0);
    for(int i=0; i+1<18; i++){
        for(int v=1; v<=n; v++){
            if(p[i][v]<0) p[i+1][v]=-1;
            else p[i+1][v]=p[i][p[i][v]];
        }
    }
}
int lca(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=0; i<18; i++){
        if(dep[v]-dep[u]>>i&1) v=p[i][v];
    }
    if(u==v) return u;
    for(int i=17; i>=0; i--){
        if(p[i][u]!=p[i][v]){
            u=p[i][u],v=p[i][v];
        }
    }
    return p[0][u];
}
int main()
{
    int u,v;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1; i<=n; i++) G[i].clear();
        for(int i=1; i<n; i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(edge{v,1});
            G[v].push_back(edge{u,0});
        }
        scanf("%d",&q);
        build();
        while(q--)
        {
            scanf("%d%d",&u,&v);
            int _lca=lca(u,v);
            int depu=dep[u]-dep[_lca];
            int depv=dep[v]-dep[_lca];
            int disu=dp[u]-dp[_lca];
            int disv=dp[v]-dp[_lca];
            if(depu==-disu&&depv==disv){
                printf("Yes\n");
            }
            else{
                printf("No\n");
            }
        }
    }
    return 0;
}