#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; struct node1{ int nxt; int to; }tree[maxn*2]; struct node2{ int nxt; int to; int LCA; }qtree[maxn*2]; int head1[maxn],cnt1; void add1(int x,int y){ tree[++cnt1].nxt=head1[x]; tree[cnt1].to=y; head1[x]=cnt1; } int head2[maxn],cnt2; void add2(int x,int y){ qtree[++cnt2].nxt=head2[x]; qtree[cnt2].to=y; head2[x]=cnt2; } int vis[maxn]; int fa[maxn]; int fifa(int x){ if(x!=fa[x]) return fa[x]=fifa(fa[x]); } void Tarjan(int x){ vis[x]=1; for(int i=head1[x];i;i=tree[i].nxt){ int v=tree[i].to; if(vis[v]) continue; Tarjan(v); fa[v]=x; } for(int i=head2[x];i;i=qtree[i].nxt){ int v=qtree[i].to; if(vis[v]){ qtree[i].LCA=fifa(v); if(i%2){ qtree[i+1].LCA=qtree[i].LCA; } else qtree[i-1].LCA=qtree[i].LCA; } } } int T,ljb,n,m,k,x,y; int main(){ scanf("%d",&T); while(T--){ ljb++; scanf("%d",&n); memset(head1,0,sizeof(head1)); memset(head2,0,sizeof(head2)); cnt1=0,cnt2=0; memset(qtree,0,sizeof(qtree)); memset(tree,0,sizeof(tree)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++){ scanf("%d",&m); for(int j=1;j<=m;j++){ scanf("%d",&x); add1(x,i); add1(i,x); } } scanf("%d",&k); for(int i=1;i<=k;i++){ scanf("%d%d",&x,&y); add2(x,y); add2(y,x); } Tarjan(1); printf("Case %d:\n",ljb); for(int i=1;i<=k;i++){ printf("%d\n",qtree[i*2].LCA); } } return 0; }
Tarjan求LCA,打起来真的爽