Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define mx 100006
- #define ll long long int
- vector<ll>vec[mx];
- ll p[mx][23],d[mx],t[mx],u,v,n;
- bool vis[mx];
- void dfs(ll s,ll dep)
- {
- for(int i=0;i<vec[s].size();i++){
- ll x=vec[s][i];
- if(vis[x]==false){
- t[x]=s;
- d[x]=dep+1;
- vis[x]=true;
- dfs(x,dep+1);
- }
- }
- }
- void init()
- {
- memset(p,-1,sizeof(p));
- for(int i=1;i<=n;i++){
- p[i][0]=t[i];
- }
- for(int i=0;i<18;i++){
- for(int j=1;j<=n;j++){
- if(p[j][i-1]!=-1){
- p[j][i]=p[p[j][i-1]][i-1];
- }
- }
- }
- }
- void query( int u, int v)
- {
- if(d[v]<d[u]){
- swap(u,v);
- }
- int dif=d[v]-d[u];
- int lev;
- while(1){
- if(d[u]==d[v]){
- break;
- }
- else{
- v=p[v][0];
- }
- }
- if(u==v){
- printf("%lld\n",u);
- }
- else{
- int x=t[u];
- for(int i=18;i>=0;i--){
- if(p[v][i]!=p[u][i]){
- v=p[v][i];
- u=p[u][i];
- }
- }
- printf("%d\n",t[v]);
- }
- }
- int main()
- {
- ll tt,c=1;
- scanf("%lld",&tt);
- while(tt--){
- memset(vis,false,sizeof(vis));
- memset(p,0,sizeof(p));
- memset(vec,0,sizeof(vec));
- memset(t,0,sizeof(t));
- memset(d,0,sizeof(d));
- scanf("%lld",&n);
- for(int i=1;i<=n;i++){
- ll m;
- scanf("%lld",&m);
- for(int j=0;j<m;j++){
- ll a;
- scanf("%lld",&a);
- vec[i].push_back(a);
- }
- }
- d[1]=0;
- t[1]=-1;
- dfs(1,0);
- init();
- ll q;
- printf("Case %lld:\n",c++);
- scanf("%lld",&q);
- while(q--){
- ll a,b;
- scanf("%lld%lld",&a,&b);
- query(a,b);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement