这是一道只要前置技能解锁足够即可AC的题 可以BJ不够 泪 我怎么可以不会点双呢。。。
点双缩点 每次建虚树 做完了
#include<cmath> #include<ctime> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<set> #include<map> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void print(int x) {if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');} const int N=200100; int n,m,tot; namespace graph { int last[N<<1],ecnt; struct EDGE{int to,nt;}e[N<<3]; inline void add(int u,int v) {e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;} int dfn[N<<1],val[N<<1],dep[N<<1],tim; int anc[N<<1][20]; void dfs(int u) { dfn[u]=++tim; for(int i=1;(1<<i)<=dep[u];++i) anc[u][i]=anc[anc[u][i-1]][i-1]; for(int i=last[u],v;i;i=e[i].nt) if((v=e[i].to)!=anc[u][0]) dep[v]=dep[u]+1, val[v]+=val[u], anc[v][0]=u, dfs(v); } inline int getlca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); int len(dep[u]-dep[v]); for(int i=0;(1<<i)<=len;++i) if((1<<i)&len) u=anc[u][i]; if(u==v) return u; for(int i=19;~i;--i) if(anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i]; return anc[u][0]; } void init() { ecnt=tim=0; memset(val,0,sizeof(val)); memset(dep,0,sizeof(dep)); memset(anc,0,sizeof(anc)); memset(last,0,sizeof(last)); } } int last[N],ecnt; struct EDGE{int to,nt;}e[N<<2]; inline void add(int u,int v) {e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;} int dfn[N],low[N],tim; int st[N],top; void tarjan(int u) { dfn[u]=low[u]=++tim, graph::val[u]=1, st[++top]=u; for(int i=last[u],v;i;i=e[i].nt) if(!dfn[v=e[i].to]) { tarjan(v),low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]) { tot++; int tmp(0); do { tmp=st[top--]; graph::add(tmp,tot), graph::add(tot,tmp); }while(tmp!=v); graph::add(u,tot),graph::add(tot,u); } } else low[u]=min(low[u],dfn[v]); } inline bool cmp(int x,int y) {return graph::dfn[x]<graph::dfn[y];} inline void insert(int &res,int x,int y) {res+=graph::val[x]-graph::val[y];} int get_ans(int *s) { register int i,grd,res(0); sort(s+1,s+1+s[0],cmp); int root=graph::getlca(s[1],s[s[0]]); st[1]=root,top=1; for(i=1;i<=s[0];++i) { grd=graph::getlca(s[i],st[top]); while(1) { if(graph::dep[st[top-1]]<=graph::dep[grd]) { insert(res,st[top],grd);top--; if(st[top]!=grd) st[++top]=grd; break; } insert(res,st[top],st[top-1]),top--; } if(s[i]!=st[top]) st[++top]=s[i]; } while(top>1) insert(res,st[top],st[top-1]),top--; return res+(root<=n)-s[0]; } int s[N]; void solve() { register int i,u,v; tot=n=read(),m=read(); for(i=1;i<=m;++i) u=read(),v=read(), add(u,v),add(v,u); tarjan(1); graph::dfs(1); int Q=read(); while(Q--) { s[0]=read(); for(i=1;i<=s[0];++i) s[i]=read(); print(get_ans(s)),puts(""); } } void initial() { graph::init(); tim=top=ecnt=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(last,0,sizeof(last)); } int main() { int T=read(); while(T--) initial(),solve(); return 0; }
