---
title: Codeforce 1276 B. Two Fairs 解析(思維、DFS、組合)
description: "Codeforce 1276 B. Two Fairs 解析(思維、DFS、組合)"
---

<!-- toc -->

# Codeforce 1276 B. Two Fairs 解析(思維、DFS、組合)
今天我們來看看CF1276B
[題目連結](https://codeforces.com/problemset/problem/1276/B)

> **題目**
給一個連通圖，並給兩個點($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](https://codeforces.com/contest/1276/submission/90363209)