AtCoder ABC #152 : F - Tree and Constraints

包除原理の良い練習。
https://atcoder.jp/contests/abc152/tasks/abc152_f

問題

N頂点の気をなすグラフが与えられる。
各辺を白黒に塗るとき、その塗り方は2^(N-1)通りある。
ここでM個の条件が与えられる。
各条件は指定された2頂点を結ぶ最短パスにおいて、1個以上の辺が黒くなければいけないことを意味する。
条件を満たす塗り方は何通りか。

解法

Mが小さいことを利用しよう。
M個のうちあるいくつかが条件に反している場合を数え、包除原理の要領で加減算する。
反する条件の一覧が分かれば、ようはそこに含まれる辺はすべて白くなければならず、その他は白黒どうでもよいので容易にその数を求められる。

int N;
int A[51],B[51];
int M;
int U[21],V[21];
vector<pair<int,ll>> E[51];
ll P[51][51];
ll C[21];

void dfs(int cur,int pre,int id,ll m) {
	P[id][cur]=m;
	FORR(e,E[cur]) if(e.first!=pre) dfs(e.first,cur,id,m|e.second);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
		E[A[i]].push_back({B[i],1LL<<i});
		E[B[i]].push_back({A[i],1LL<<i});
	}
	FOR(i,N) dfs(i,i,i,0);
	
	cin>>M;
	FOR(i,M) {
		cin>>x>>y;
		C[i]=P[x-1][y-1];
	}
	
	ll ret=0;
	int mask;
	FOR(mask,1<<M) {
		ll m=0;
		FOR(i,M) if(mask&(1<<i)) m|=C[i];
		ll pat=1LL<<(N-1-__builtin_popcountll(m));
		if(__builtin_popcount(mask)%2==0) {
			ret+=pat;
		}
		else {
			ret-=pat;
		}
		
	}
	cout<<ret<<endl;
}

まとめ

方針はすぐ立つんだけど、細かいところミスしそうで怖いんだよな。