标准lca板子，只用来求最近公共祖先
T组输入，最后一行输入一个查询。
#include
#define pb push_back
using namespace std ;
int T,n;
int fa[10005][16],dep[10005],d[10005];
vector <int > e [10005];
void dfs(int u){for(int i=1;i<=15;i++){fa[u][i]=fa[fa[u][i-1]][i-1];}for(int i=0;i<e[u].size();i++){int v= e[u][i];dep[v]=dep[u]+1;fa[v][0]= u ; dfs(v);}
}
int lca(int u,int v){if(dep[u]>dep[v]) swap(u,v);int t = dep[v] - dep [u];for(int i=15;i>=0;i--)if((1<<i)&t) v=fa[v][i];if(u==v) return u;for(int i=15;i>=0;i--){if(fa[u][i]!=fa[v][i])u = fa[u][i],v=fa[v][i];}return fa[u][0];
}
int main()
{scanf("%d",&T);while(T--){memset(dep,0,sizeof(dep));memset(fa,0,sizeof(fa));memset(d,0,sizeof(d));scanf("%d",&n);int u,v;for(int i=1;i<n;i++){scanf("%d %d",&u,&v);e[u].pb(v);d[v]++;}scanf("%d %d",&u,&v);int rt=0;for(int i=1;i<=n;i++){if(!d[i]) rt = i ;}dfs(rt);cout<<lca(u,v)<<endl;for(int i=1;i<=n;i++){e[i].clear();}}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
