战略游戏：

题目描述

省选临近，放飞自我的小Q无心刷题，于是怂恿小C和他一起颓废，玩起了一款战略游戏。

这款战略游戏的地图由n个城市以及m条连接这些城市的双向道路构成，并且从任意一个城市出发总能沿着道路走到任意其他城市。现在小C已经占领了其中至少两个城市，小Q可以摧毁一个小C没占领的城市，同时摧毁所有连接这个城市的道路。只要在摧毁这个城市之后能够找到某两个小C占领的城市u和v，使得从u出发沿着道路无论如何都不能走到v，那么小Q就能赢下这一局游戏。

小Q和小C一共进行了q局游戏，每一局游戏会给出小C占领的城市集合S

你需要帮小Q数出有多少个城市在他摧毁之后能够让他赢下这一局游戏。

输入

第一行包含一个正整数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

输出

对于每一局游戏，输出一行，包含一个整数，表示这一局游戏中有多少个城市在小Q摧毁之后能够让他赢下这一局游戏。

样例输入

2

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

样例输出

0

1

3

0

1

2

3

题意：

无向连通图，

有q个询问，每次给出一点集S

求能使S任意两点不连通的点数(S中的点除外)。

思路：

是谁在上面放了一个虚树标签，害得蒟蒻学了半天的虚树。

其实并不需要虚树。

我们先用圆方树将图转化为树，

题目就变成了求包含这些点的最小子图的点数-|S|。

“求包含这些点的最小子图”我们可以用虚树，

但这里并不需要树型DP。

所以我们将点按dfs序排序，求出相邻两点之间的距离和，

因为每条边会遍历两边，所以最后除以2就行。

当然，这个子图中深度最低的点可能是圆点，我们需要加1。

代码：

 

1 #include
     
       2 #define re register 3 using namespace std; 4 const int N=2e5+6,M=4e5+6; 5 int n,m,cnt,deep,top,t1,t2,q,p,ans,c; 6 int head[N],head2[N<<1],dfn[N],low[N],s[N<<1],w[N<<1],f[N<<1][22],d[N<<1],x[N<<1]; 7 struct edge 8 { 9     int nxt,to;10 }e[M],g[M];11 inline void add(int u,int v){e[++cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt;}12 inline void add2(int u,int v){g[++cnt].nxt=head2[u]; g[cnt].to=v; head2[u]=cnt;}13 inline int read()14 {15     int T=0,F=1; char ch=getchar();16     while(ch<'0'||ch>'9'){
   if(ch=='-') F=-1; ch=getchar();}17     while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();18     return F*T;19 }20 void tarjan(int u)21 {22     //cout<
      <
       
        =dfn[u])31             {32                 ++t1; w[t1]=0; add2(u,t1);33                 while(s[top+1]!=t) add2(t1,s[top]),--top;34             }35         }36         else low[u]=min(low[u],dfn[t]);37     }38 }39 void dfs(int u,int fa)40 {41     f[u][0]=fa; d[u]=d[fa]+1; w[u]+=w[fa]; dfn[u]=++cnt;42     for(int i=1;i<=20;++i) f[u][i]=f[f[u][i-1]][i-1];43     for(int i=head2[u];i;i=g[i].nxt) dfs(g[i].to,u);44 }45 inline int lca(int u,int v)46 {47     if(d[u]
        
         =0;--i) if(d[u]>=d[v]+(1<
         
          =0;--i)51     {52         if(f[u][i]==f[v][i]) continue;53         u=f[u][i],v=f[v][i];54     }55     return f[u][0];56 }57 inline int dis(int u,int v){
   int o=lca(u,v); return w[u]-w[o]+w[v]-w[o];}58 bool cmp(int u,int v){
   return dfn[u]