bzoj

luogu

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$表示第$u$個城市和第$v$個城市之間有一條道路，同一對城市之間可能有多條道路連接配接，

第$m+1$行是一個整數$q$，表示遊戲的局數，

接下來$q$行，每行先給出一個整數$|S|(2\le |S|\le n)$

表示小C占領的城市數量，然後給出$|S|$個整數$s1,s2,...s|S|,(1\le s1<s2<s_{|S|}\le n)$，表示小C占領的城市。

$1\le T \le 10$

$2\le n\le 10^5$ 且$ n-1\le m\le 2*10^5$，

$1\le q\le 10^5$，

對于每組測試資料，有$\sum |S|\le 2*10^5$

Output

對于每一局遊戲，輸出一行，包含一個整數，表示這一局遊戲中有多少個城市在小Q摧毀之後能夠讓他赢下這一局遊戲。

Sample Input

7 6

1 2

1 3

2 4

2 5

3 6

3 7

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

3 1 2 3

3 1 2 6

3 1 5 6

3 4 5 6

Sample Output

sol

這種題基本上可以一眼秒出是圓方樹+虛樹吧。。。

怎麼算答案？

就是用給定的點建出虛樹後每條邊的長度之和吧。因為切斷這棵虛樹上的任意一條邊都是符合題意的。

是以維護一下路徑上有多少個圓點即可。

code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 4e5+5;
int n,tot,m,Q,dfn[N],low[N],tim,S[N];
int fa[N],dep[N],dis[N],sz[N],son[N],top[N],s[N],q[N];
struct Graph{
    int to[N],nxt[N],head[N],cnt;
    void init(){
        memset(head,0,sizeof(head));
        cnt=0;
    }
    void link(int u,int v){
        to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
        to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
    }
}G1,G2;
void Tarjan(int u){
    dfn[u]=low[u]=++tim;S[++S[0]]=u;
    for (int e=G1.head[u];e;e=G1.nxt[e]){
        int v=G1.to[e];
        if (!dfn[v]){
            Tarjan(v),low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]){
                G2.link(++tot,u);int x=0;
                do{
                    x=S[S[0]--];G2.link(tot,x);
                }while (x!=v);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
void dfs1(int u,int f){
    fa[u]=f;dep[u]=dep[f]+1;dis[u]=dis[f]+(u<=n);sz[u]=1;
    for (int e=G2.head[u];e;e=G2.nxt[e]){
        int v=G2.to[e];if (v==f) continue;
        dfs1(v,u);sz[u]+=sz[v];
        if (sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int up){
    top[u]=up;dfn[u]=++tim;
    if (son[u]) dfs2(son[u],up);
    for (int e=G2.head[u];e;e=G2.nxt[e]){
        int v=G2.to[e];if (v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
    low[u]=tim;
}
int getlca(int u,int v){
    while (top[u]^top[v]){
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
bool cmp_dfn(int i,int j){return dfn[i]<dfn[j];}
int main(){
    int T=gi();while (T--){
        tot=n=gi();m=gi();G1.init();G2.init();tim=0;
        while (m--){
            int u=gi(),v=gi();
            G1.link(u,v);
        }
        memset(dfn,0,sizeof(dfn));
        memset(son,0,sizeof(son));
        for (int i=1;i<=n;++i) if (!dfn[i]) Tarjan(i);
        tim=0,dfs1(1,0),dfs2(1,1);
        Q=gi();while (Q--){
            int k=gi(),len=k,tp=0,ans=0;
            for (int i=1;i<=k;++i) s[i]=gi();
            sort(s+1,s+k+1,cmp_dfn);
            for (int i=1;i<k;++i) s[++len]=getlca(s[i],s[i+1]);
            sort(s+1,s+len+1,cmp_dfn);len=unique(s+1,s+len+1)-s-1;
            ans=s[1]<=n;
            for (int i=1;i<=len;++i){
                while (tp&&low[q[tp]]<dfn[s[i]]) --tp;
                if (tp) ans+=dis[s[i]]-dis[q[tp]];
                q[++tp]=s[i];
            }
            printf("%d\n",ans-k);
        }
    }
    return 0;
}

轉載于:https://www.cnblogs.com/zhoushuyu/p/9087842.html

[BZOJ5329][SDOI2018]戰略遊戲Descriptionsolcode