提交时间:2024-08-30 15:32:49
运行 ID: 32056
#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,fa[maxn][18],dfn[maxn],siz[maxn],son[maxn],rnk[maxn],dep[maxn],top[maxn],ct; vector<pi>G; vector<int>v[maxn],vv[maxn],g[maxn];int deg[maxn]; int lca(int x,int y){ if(x==n+1)return y;if(y==n+1)return x; if(dep[x]>dep[y])swap(x,y); down(i,17,0)if(dep[fa[y][i]]>=dep[x])y=fa[y][i]; if(x==y)return x; down(i,17,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void topo(){ up(i,1,n)fa[i][0]=n+1; queue<int>q;up(i,1,n)if(!deg[i])q.push(i),fa[i][0]=0,g[0].p_b(i); while(!q.empty()){ int x=q.front();q.pop(); dep[x]=dep[fa[x][0]]+1,g[fa[x][0]].p_b(x); up(i,1,17)fa[x][i]=fa[fa[x][i-1]][i-1]; for(int y:vv[x]){ fa[y][0]=lca(fa[y][0],x); if(!(--deg[y]))q.push(y); } } } void dfs(int u){dfn[u]=++ct; for(int x:g[u])dfs(x); } void slv(){ n=read(); up(i,1,n){ int c=read(); while(c--)v[i].p_b(read()); }up(i,1,n)for(int x:v[i])vv[x].p_b(i); up(i,1,n)deg[i]=v[i].size(); topo(); //up(i,1,n)cout<<"test "<<fa[i][0]<<"\n"; dfs(0); int q=read(); while(q--){ int k=read();G.clear(); up(i,1,k){ int x=read();G.p_b(m_p(dfn[x],x)); }sort(G.begin(),G.end()); int res=0; up(i,0,k-1){ res+=dep[G[i].p2]; if(i!=k-1)res-=dep[lca(G[i].p2,G[i+1].p2)]; }printf("%d\n",res); } }int main(){ //freopen("set.in","r",stdin); //freopen("set.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; } /* */