/* 先来个倍增 */ #include<iostream> #include<cstring> #include<cstdio> #define maxn 10010 using namespace std; int T,n,num,head[maxn],st,end,anc,fa[maxn][25],dep[maxn],out[maxn],root; struct node { int u,v,t,pre; }e[maxn*2]; void Add(int from,int to) { num++; e[num].u=from; e[num].v=to; e[num].pre=head[from]; head[from]=num; } void Dfs(int now,int from,int c) { fa[now][0]=from; dep[now]=c; for(int i=head[now];i;i=e[i].pre) if(e[i].v!=from) Dfs(e[i].v,now,c+1); } void Get_fa() { for(int j=1;j<=16;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; } int Get_same(int a,int t) { for(int i=1;i<=t;i++) a=fa[a][0]; return a; } int LCA(int a,int b) { if(dep[a]<dep[b])swap(a,b); a=Get_same(a,dep[a]-dep[b]); if(a==b)return a; for(int i=16;i>=0;i--) if(fa[a][i]!=fa[b][i]) { a=fa[a][i];b=fa[b][i]; } return fa[a][0]; } int main() { scanf("%d",&T); while(T--) { memset(head,0,sizeof(head)); memset(fa,0,sizeof(fa)); memset(out,0,sizeof(out)); memset(dep,0,sizeof(dep)); num=0;root=0; scanf("%d",&n); int x,y; for(int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); Add(x,y);Add(y,x); out[y]=1; } for(int i=1;i<=n;i++) if(out[i]==0)root=i; Dfs(root,root,0); Get_fa(); scanf("%d%d",&st,&end); anc=LCA(st,end); printf("%d ",anc); } return 0; }
/* 离线Tarjan 我们Dfs整张图的时候 对于一组u v 我们一定按照 u s v 的顺序跑完 此时u v 在以s为根的子树里 那么我们借助并茶几 将u v的fa 的anc赋值为s 这样我们查询u v 的时候就能找到s 如果我们求 st end 的lca 当我们遍历到st 或者end的时候 只需要判断另一个是不是已经被访问过 */ #include<iostream> #include<cstdio> #include<cstring> #include<vector> #define maxn 100010 using namespace std; int T,n,m,fa[maxn],st,end,anc[maxn]; vector<int>a[maxn]; int root[maxn],f[maxn]; void init() { scanf("%d",&n); int x,y; for(int i=1;i<=n;i++) { fa[i]=i;root[i]=1; } for(int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); a[x].push_back(y); fa[y]=x;root[y]=0; } } int find(int x) { if(x!=fa[x])fa[x]=find(fa[x]); return fa[x]; } void Union(int x,int y) { int r1=find(x); int r2=find(y); if(r1!=r2)fa[r2]=r1; } void LCA(int parent) { anc[parent]=parent;//初始化自己的lca为自己 for(int i=0;i<a[parent].size();i++) { LCA(a[parent][i]); Union(parent,a[parent][i]); anc[find(parent)]=parent;//把自己和自己子孙们的lca赋值为它 } f[parent]=1; if(st==parent&&f[end]==1) { printf("%d ",anc[find(end)]); return; } if(end==parent&&f[st]==1) { printf("%d ",anc[find(st)]); return; } } int main() { scanf("%d",&T); while(T--) { memset(f,0,sizeof(f)); memset(a,0,sizeof(a)); init(); scanf("%d%d",&st,&end); for(int i=1;i<=n;i++) if(root[i]) LCA(i); } return 0; }