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