Codeforces #606 Div1 B. Two Fairs

タイトルの意味は何なんだろう。
https://codeforces.com/contest/1276/problem/B

問題

連結無向グラフと、頂点A,Bが与えられる。
A・Bの両方を通ることなくパスを張れる頂点対(U,V)は何組あるか。

解法

Aを含まないグラフGaと、Bを含まないグラフGbを考え、それぞれ連結成分の数を取る。
ある頂点UからA・Bの両方を通らず移動できる頂点の数、(Gaで連結な頂点群)+(Gbで連結な頂点群)-(GaでもGbでも連結な頂点群)なので、Union-Findを2つ持ってそれぞれ数え上げよう。

int T;
int N,M,A,B;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<505050> As,Bs;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>A>>B;
		A--;
		B--;
		
		As.reinit(N);
		Bs.reinit(N);
		FOR(i,M) {
			cin>>x>>y;
			x--,y--;
			if(x!=A && y!=A) As(x,y);
			if(x!=B && y!=B) Bs(x,y);
		}
		
		map<int,int> PA,PB;
		map<pair<int,int>,int> PAB;
		ll ret=0;
		int oth=0;
		FOR(i,N) if(i!=A && i!=B) {
			ret+=oth-PA[As[i]]-PB[Bs[i]]+PAB[{As[i],Bs[i]}];
			PA[As[i]]++;
			PB[Bs[i]]++;
			PAB[{As[i],Bs[i]}]++;
			oth++;
		}
		cout<<ret<<endl;
		
		
	}
}

まとめ

本番Aよりこっちの方がラクに解いてる。