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

今天我們來看看CF1276B

題目連結

題目

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

想法

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

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

1. \(a,b\)都走得到的
2. 只有\(a\)走得到
3. 只有\(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