5329: [Sdoi2018]战略游戏
Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 12 Solved: 9
[Submit][Status][Discuss]
Description
省选临近，放飞自我的小Q无心刷题，于是怂恿小C和他一起颓废，玩起了一款战略游戏。
这款战略游戏的地图由n个城市以及m条连接这些城市的双向道路构成，并且从任意一个城市出发总能沿着道路走到
任意其他城市。现在小C已经占领了其中至少两个城市，小Q可以摧毁一个小C没占领的城市，同时摧毁所有连接这
个城市的道路。只要在摧毁这个城市之后能够找到某两个小C占领的城市u和v，使得从u出发沿着道路无论如何都不
能走到v，那么小Q就能赢下这一局游戏。
小Q和小C一共进行了q局游戏，每一局游戏会给出小C占领的城市集合S
你需要帮小Q数出有多少个城市在他摧毁之后能够让他赢下这一局游戏。
Input
第一行包含一个正整数T，表示测试数据的组数，
对于每组测试数据，
第一行是两个整数n和m，表示地图的城市数和道路数，
接下来m行，每行包含两个整数u和v~(1<=u<v<=n)
表示第u个城市和第v个城市之间有一条道路，同一对城市之间可能有多条道路连接，
第m+1是一个整数q，表示游戏的局数，
接下来q行，每行先给出一个整数|S|(2<=|S|<=n)
表示小C占领的城市数量，然后给出|S|个整数s1,s2,...s|S|,(1<=s1<s2<s|S|<=n)，表示小C占领的城市。
1<= T<= 10，
2<= n<= 10^5 且 n-1<= m<= 2*10^5，
1<= q<= 10^5，
对于每组测试数据，有Sigma|S|<= 2*10^5
Output
对于每一局游戏，输出一行，包含一个整数，表示这一局游戏中有多少个城市在小Q摧毁之后能够让他赢下这一局游戏。
Sample Input
7 6
1 2
1 3
2 4
2 5
3 6
3 7
3
2 1 2
3 2 3 4
4 4 5 6 7
6 6
1 2
1 3
2 3
1 4
2 5
3 6
4
3 1 2 3
3 1 2 6
3 1 5 6
3 4 5 6
1 2
1 3
2 4
2 5
3 6
3 7
3
2 1 2
3 2 3 4
4 4 5 6 7
6 6
1 2
1 3
2 3
1 4
2 5
3 6
4
3 1 2 3
3 1 2 6
3 1 5 6
3 4 5 6
Sample Output
0
1
3
0
1
2
3
1
3
0
1
2
3
考场上想出来发现是个圆方树。。。但是以前没写过怎么办啊QWQ
不管了，硬钢吧23333
(然后最后就神奇的钢出来了)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stack>
#include<vector>
#include<map>
#include<tr1/unordered_map>
#define ll long long
#define pb push_back
#define mid (l+r>>1)
#define lc (o<<1)
#define rc ((o<<1)|1)
using namespace std;
using namespace std::tr1;
const int maxn=400005;
vector<int> g[maxn];
unordered_map<int,int> mmp[maxn];
int T,n,m,num,hd[maxn],to[maxn*2],ne[maxn*2];
int dfn[maxn],low[maxn],dc,cnt,rp[maxn],dy[maxn],dep[maxn];
int siz[maxn],son[maxn],cl[maxn],F[maxn],L,Q,now[maxn],k,ans;
int Lim[maxn*4],sum[maxn*4],le,ri,W,tag[maxn*4];
struct lines{ int U,V;};
stack<lines> s;
inline int read(){
int x=0; char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}
void Wt(int x){ if(x<0) { Wt(-x); return;} if(x>=10) Wt(x/10); putchar(x%10+'0');}
inline void add(int x,int y){ to[++num]=y,ne[num]=hd[x],hd[x]=num;}
inline void ADD(int x,int y){ g[x].pb(y),g[y].pb(x);}
inline void init(){
for(int i=0;i<=cnt;i++) g[i].clear(),mmp[i].clear();
memset(hd,0,sizeof(hd)),num=0;
memset(dfn,0,sizeof(dfn)),dc=0;
memset(son,0,sizeof(son));
}
void dfs(int x,int fa){
low[x]=dfn[x]=++dc;
lines e;
for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa){
e=(lines){x,to[i]};
if(!dfn[to[i]]){
s.push(e);
dfs(to[i],x),low[x]=min(low[x],low[to[i]]);
if(low[to[i]]>=dfn[x]){
cnt++;
for(;;){
e=s.top(),s.pop();
if(!mmp[e.U].count(cnt)) ADD(e.U,cnt),mmp[e.U][cnt]=1;
if(!mmp[e.V].count(cnt)) ADD(e.V,cnt),mmp[e.V][cnt]=1;
if(e.U==x&&e.V==to[i]) break;
}
}
}
else if(dfn[to[i]]<low[x]){
low[x]=dfn[to[i]];
s.push(e);
}
}
}
void dfs1(int x,int fa){
F[x]=fa,siz[x]=1;
for(int i=g[x].size()-1,T;i>=0;i--){
T=g[x][i];
if(T==fa) continue;
rp[T]=rp[x]+(T<=n),dep[T]=dep[x]+1;
dfs1(T,x),siz[x]+=siz[T];
if(!son[x]||siz[son[x]]<siz[T]) son[x]=T;
}
}
void dfs2(int x,int tp){
cl[x]=tp,dfn[x]=++dc,dy[dc]=x;
if(!son[x]) return;
dfs2(son[x],tp);
for(int i=g[x].size()-1,t;i>=0;i--){
T=g[x][i];
if(T==F[x]||T==son[x]) continue;
dfs2(T,T);
}
}
void build(int o,int l,int r){
sum[o]=tag[o]=0;
if(l==r){ Lim[o]=(dy[l]<=n); return;}
build(lc,l,mid),build(rc,mid+1,r);
Lim[o]=Lim[lc]+Lim[rc];
}
inline void work1(int o){ sum[o]=Lim[o],tag[o]=1;}
inline void work2(int o){ sum[o]=0,tag[o]=2;}
inline void pushdown(int o){
if(tag[o]==1){ work1(lc),work1(rc);}
else if(tag[o]){ work2(lc),work2(rc);}
tag[o]=0;
}
inline void maintain(int o){
sum[o]=sum[lc]+sum[rc];
}
void update1(int o,int l,int r){
if(l>=le&&r<=ri){ ans+=Lim[o]-sum[o],work1(o); return;}
pushdown(o);
if(le<=mid) update1(lc,l,mid);
if(ri>mid) update1(rc,mid+1,r);
maintain(o);
}
void update2(int o,int l,int r){
if(l>=le&&r<=ri){ work2(o); return;}
pushdown(o);
if(le<=mid) update2(lc,l,mid);
if(ri>mid) update2(rc,mid+1,r);
maintain(o);
}
inline int LCA(int x,int y){
while(cl[x]!=cl[y]){
if(dep[cl[x]]>dep[cl[y]]) x=F[cl[x]];
else y=F[cl[y]];
}
return dep[x]>dep[y]?y:x;
}
inline void paint(int x){
while(x){
le=dfn[cl[x]],ri=dfn[x];
update1(1,1,cnt);
x=F[cl[x]];
}
}
inline void REV(int x){
while(x){
le=dfn[cl[x]],ri=dfn[x];
update2(1,1,cnt);
x=F[cl[x]];
}
}
inline void solve(){
/*
for(int i=1;i<=cnt;i++){
cout<<i<<':'<<g[i].size()<<endl;
for(int j=g[i].size()-1;j>=0;j--) printf("%d ",g[i][j]);
puts("");
}
*/
memset(dfn,0,sizeof(dfn)),dc=0;
rp[1]=1,dfs1(1,0),dfs2(1,1);
build(1,1,cnt);
Q=read();
while(Q--){
ans=L=0,k=read();
for(int i=1;i<=k;i++){
now[i]=read();
if(!L) L=now[i]; else L=LCA(L,now[i]);
paint(now[i]);
}
Wt(ans-rp[F[L]]-k),puts("");
for(int i=1;i<=k;i++) REV(now[i]);
}
}
int main(){
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int uu,vv;
T=read();
while(scanf("%d%d",&n,&m)==2){
init(),cnt=n;
for(int i=1;i<=m;i++){
uu=read(),vv=read();
add(uu,vv),add(vv,uu);
}
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,-1);
solve();
}
return 0;
}