提交时间:2024-08-30 16:47:01
运行 ID: 32066
#include<bits/stdc++.h> using namespace std; #define int long long #define lson (pos<<1) #define rson (pos<<1|1) #define pii pair<int,int> #define fr first #define sc second #define inx int I=h[u],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}x=c-'0';c=getchar();while(c<='9'&&c>='0'){x*=10;x+=c-'0';c=getchar();}return x*f;} const int MAXN=300010,N=20,inf=1000000000; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT; void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;} int n,Mc,q,d[MAXN],p[MAXN],dep[MAXN],f[MAXN][N+5]; queue<int>Q; int lca(int u,int v){ if(dep[u]<dep[v])swap(u,v); for(int i=N;~i;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i]; if(u==v)return u; for(int i=N;~i;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i]; return f[u][0]; } void bfs(){ Q.push(0); while(!Q.empty()){ int u=Q.front();Q.pop(); f[u][0]=p[u]; if(u)dep[u]=dep[p[u]]+1; for(int i=1;i<=N;i++)f[u][i]=f[f[u][i-1]][i-1]; for(inx){ if(p[v]!=-1)p[v]=lca(p[v],u); else p[v]=u; d[v]--; if(!d[v])Q.push(v); } } memset(h,0,sizeof(h));CNT=0; for(int i=1;i<=n;i++)add_side(p[i],i); } int dfn[MAXN],cnt; void dfs(int u,int lst){ dfn[u]=++cnt; for(inx)if(v!=lst){ dfs(v,u); } } bool cmp(int x,int y){return dfn[x]<dfn[y];} int b[MAXN]; void slv(){ n=read(); for(int i=1;i<=n;i++){ int x=read();d[i]=x,p[i]=-1; while(x--){ int tmp=read(); add_side(tmp,i); } } q=read(); for(int i=1;i<=n;i++)if(!d[i])add_side(0,i),d[i]++; bfs();dfs(0,0); while(q--){ int x=read(); if(!x){ printf("0\n"); continue; } for(int i=1;i<=x;i++)b[i]=read(); sort(b+1,b+x+1,cmp); int ans=dep[b[1]]; for(int i=2;i<=x;i++){ ans+=dep[b[i]]-dep[lca(b[i-1],b[i])]; } printf("%lld\n",ans); } } signed main(){ slv(); return 0; }