提交时间:2024-08-30 14:46:33
运行 ID: 32040
#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],fa[maxn],dfn[maxn],siz[maxn],son[maxn],rnk[maxn],dep[maxn],top[maxn],ct; int fd(int x){ if(x==fa[x])return x; return fa[x]=fd(fa[x]); }vector<pi>G; struct SegTree { struct node { int len,sm,lz; }d[maxn<<3]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define len(p) d[p].len #define sm(p) d[p].sm #define lz(p) d[p].lz void pu(int p){if(lz(p))sm(p)=len(p);else sm(p)=sm(ls(p))+sm(rs(p));} void bd(int l,int r,int p){ len(p)=r-l+1; if(l==r)return; int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p)); }void modify(int l,int r,int s,int t,int p,int x){ if(l<=s&&t<=r){ lz(p)+=x;pu(p);return; }int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),x);if(r>=mid+1)modify(l,r,mid+1,t,rs(p),x);pu(p); } }T; vector<int>v[maxn],g[maxn]; void dfs(int u){ siz[u]=1; for(int x:g[u]){ dep[x]=dep[u]+1;dfs(x);siz[u]+=siz[x]; if(siz[x]>siz[son[u]])son[u]=x; } }void dfs2(int u,int tp){ dfn[u]=++ct,rnk[ct]=u,top[u]=tp; if(!son[u])return;dfs2(son[u],tp); for(int x:g[u])if(x!=son[u])dfs2(x,x); }void modify(int x){ while(x){ int u=top[x]; G.p_b(m_p(dfn[u],dfn[x])); T.modify(dfn[u],dfn[x],1,n,1,1); x=FA[u]; } } int tag[1005][1005],tg[1005]; void sub1(){ up(i,1,n){ if(v[i].empty()){ tag[i][i]=1;continue; } up(j,1,i)tag[i][j]=1; for(int x:v[i]){ up(j,1,i-1)tag[i][j]&=tag[x][j]; } }int q=read(); while(q--){ int k=read();up(i,1,n)tg[i]=0; while(k--){ int x=read(); up(i,1,n)tg[i]|=tag[x][i]; }int cnt=0; up(i,1,n)if(tg[i])cnt++; printf("%d\n",cnt); } } void slv(){ n=read(); up(i,1,n){ int c=read(); while(c--)v[i].p_b(read()); if(v[i].empty())dep[i]=1; else dep[i]=dep[v[i][0]]+1,FA[i]=v[i][0],g[FA[i]].p_b(i); }if(n<=1000){ sub1();return; } set<int>rt; up(i,1,n)if(!v[i].size())rt.insert(i); //up(i,1,n)for(int x:g[i])cout<<"? "<<i<<" "<<x<<"\n"; for(int x:rt){ dep[x]=1; dfs(x),dfs2(x,x); }T.bd(1,n,1); int q=read(); while(q--){ int k=read(); G.clear();while(k--){ int c=read(); modify(c); }printf("%d\n",T.sm(1)); for(auto it:G)T.modify(it.p1,it.p2,1,n,1,-1); } }int main(){ //freopen("set.in","r",stdin); //freopen("set.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; } /* */