Codeforce 1276 B. Two Fairs 解析(思維、DFS、組合)

今天我們來看看CF1276B

題目連結

題目

給一個連通圖，並給兩個點(\(a,b\))，求有多少點對使得:任一路徑都要經過\(a,b\)這兩點。

想法

首先因為不一定是棵樹，所以總覺得LCA用不到。而這個圖又很大，因此感覺應該是要從\(a,b\)這兩點出發做點事情，例如DFS。

當開始這樣想以後，會發現我們其實可以把所有點分成三種類型:

\(a,b\)都走得到的
只有\(a\)走得到
只有\(b\)走得到

這樣最後的點對數量就是2類乘以3類。

實作起來只要從\(a,b\)分別DFS一次，不妨假設我們現在是從\(a\)開始DFS:

那麼只要遇到\(b\)時當前路徑的DFS停下來，這樣那些一定要經過\(b\)才能到的點就不可能訪問到了。

而區分以上三種類型的點，只要維護一個陣列(給每個點一個數字)，在從\(a\)開始DFS時，經過的點都加上\(1\)；從\(b\)開始DFS時，經過的點都加上\(2\)。以上就可以區分各種點了。

程式碼:

const int _n=2e5+10;

int t,n,m,a,b,u,v,ans[_n],cnt[4];

VI G[_n];

bool vis[_n];

void dfs(int v,int end,int val){

  if(v==end)return; vis[v]=1; if(v!=a and v!=b)ans[v]+=val;

  rep(i,0,SZ(G[v]))if(!vis[G[v][i]])dfs(G[v][i],end,val);

}

main(void) {cin.tie(0);ios_base::sync_with_stdio(0);

  cin>>t;while(t--){

    memset(vis,0,sizeof vis); rep(i,1,n+1)G[i].clear();

    memset(ans,0,sizeof ans); memset(cnt,0,sizeof cnt);

    cin>>n>>m>>a>>b;rep(i,0,m){cin>>u>>v;G[u].pb(v),G[v].pb(u);}

    dfs(a,b,1); memset(vis,0,sizeof vis); dfs(b,a,2);

    rep(i,1,n+1)cnt[ans[i]]++;

    cout<<1ll*cnt[1]*cnt[2]<<'\n';

  }

  return 0;

}

標頭、模板請點Submission看

Submission