这只是代码(附tarjan)，想学思路看其他题解

#include <iostream>
#include <algorithm>
using namespace std ;
const int N=40010 ;
int p[N] ;
int n,m ;
bool anc(int a,int b)
{
    if(a==b) return true ;
    else if(p[b]==b) return false ;
    return anc(a,p[b]) ;
}
int main()
{
    scanf("%d",&n) ;
    int root=0 ;
    for(int i=1;i<N;i++) p[i]=i ;
    while(n--)
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        if(b==-1) root=a ;
        else p[a]=b ;
    }
    scanf("%d",&m) ;
    while(m--)
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        if(anc(a,b)) puts("1") ;
        else if(anc(b,a)) puts("2") ;
        else puts("0") ;
    }
    return 0 ;
}

不足：代码短但时间多，TLE
30pts/100pts

//#2:邻接表,非LCA，好了那么一丢丢
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std ;
const int N=40010,M=2*N ;
int h[N],e[M],ne[M],idx ; //孩子节点
int dep[N],fa[N] ;
int n,m ;
int root ;
void add(int a,int b)
{
    e[idx]=b ;
    ne[idx]=h[a] ;
    h[a]=idx++ ;
}
bool father(int a,int b)
{
    if(dep[b]<dep[a]) return false ;
    while(dep[b]>dep[a]) b=fa[b] ;
    return a==b ;
}
void bfs()
{
    memset(dep,-1,sizeof dep) ;
    dep[root]=0 ;
    queue<int> q ;
    q.push(root) ;
    while(q.size())
    {
        int t=q.front() ;
        q.pop() ;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i] ;
            if(dep[j]==-1)
            {
                dep[j]=dep[t]+1 ;
                q.push(j) ;
            }
        }
    }
}
int main()
{
    scanf("%d",&n) ;
    memset(h,-1,sizeof h) ;
    while(n--)
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        if(b==-1) root=a ;
        else add(a,b),add(b,a),fa[a]=b ;
    }
    bfs() ;
    scanf("%d",&m) ;
    while(m--)
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        if(father(a,b)) puts("1") ;
        else if(father(b,a)) puts("2") ;
        else puts("0") ;
    }
    return 0 ;
}
//60pts/100pts TLE

为什么bfs长得像SPFA呢？

//#3:倍增,终于是LCA了！
//抛弃了原fa数组（用于存父节点），保留了邻接表，并增加了lca倍增
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std ;
const int N=40010,M=2*N ;
int h[N],e[M],ne[M],idx ; 
int dep[N],fa[N][16] ;
int n,m ;
int root ;
void add(int a,int b)
{
    e[idx]=b ;
    ne[idx]=h[a] ;
    h[a]=idx++ ;
}
int lca(int a,int b)
{
    if(dep[b]>dep[a]) swap(a,b) ;
    for(int i=15;i>=0;i--)
        if(dep[fa[a][i]]>=dep[b])
            a=fa[a][i] ;
    if(a==b) return a ;
    for(int i=15;i>=0;i--)
        if(fa[a][i]!=fa[b][i])
            a=fa[a][i],b=fa[b][i] ;
    return fa[a][0] ;
}
void bfs()
{
    memset(dep,-1,sizeof dep) ;
    dep[root]=0 ;
    queue<int> q ;
    q.push(root) ;
    while(q.size())
    {
        int t=q.front() ;
        q.pop() ;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i] ;
            if(dep[j]==-1)
            {
                dep[j]=dep[t]+1 ;
                fa[j][0]=t ;
                for(int k=1;k<=15;k++) fa[j][k]=fa[fa[j][k-1]][k-1] ;
                q.push(j) ;
            }
        }
    }
}
int main()
{
    scanf("%d",&n) ;
    memset(h,-1,sizeof h) ;
    while(n--)
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        if(b==-1) root=a ;
        else add(a,b),add(b,a) ;
    }
    bfs() ;
    scanf("%d",&m) ;
    while(m--)
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        int ans=lca(a,b) ;
        if(ans==a) puts("1") ;
        else if(ans==b) puts("2") ;
        else puts("0") ;
    }
    return 0 ;
}

Accepted/224ms

还有tarjan没讲呢！

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std ;
typedef pair<int,int> PII ;
const int N=40010,M=2*N ;
int h[N],e[M],ne[M],idx ; 
int n,m ;
int root ;
int p[N] ;
int res[M],st[N] ;
vector<PII> query[N] ;
PII request[N] ;
void add(int a,int b)
{
    e[idx]=b ;
    ne[idx]=h[a] ;
    h[a]=idx++ ;
}
int find(int x)
{
    if(x==p[x]) return x ;
    else return p[x]=find(p[x]) ;
}
void tarjan(int u)
{
    st[u]=1 ;
    for(int i=h[u];~i;i=ne[i])
        if(!st[e[i]])
        {
            tarjan(e[i]) ;
            p[e[i]]=u ;
        }
    for(auto item:query[u])
    {
        int j=item.first ;
        int id=item.second ;
        if(st[j]==2)
        {
            int fa=find(j) ;
            res[id]=fa ;
        }
    }
    st[u]=2 ;
}
int main()
{
    scanf("%d",&n) ;
    memset(h,-1,sizeof h) ;
    for(int i=1;i<=N;i++) p[i]=i ;
    for(int i=1;i<=n;i++)
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        if(b==-1) root=a ;
        else add(a,b),add(b,a) ;
    }
    scanf("%d",&m) ;
    for(int i=1;i<=m;i++)
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        query[a].push_back({b,i}) ;
        query[b].push_back({a,i}) ;
        request[i]={a,b} ;
    }
    tarjan(root) ;
    for(int i=1;i<=m;i++)
        if(res[i]==request[i].first) puts("1") ;
        else if(res[i]==request[i].second) puts("2") ;
        else puts("0") ;
    return 0 ;
}

Accepted/321ms

所以，还是做倍增比较快！