AtCoder ARC #101 : E - Ribbons on Tree

これ系苦手…。
https://beta.atcoder.jp/contests/arc101/tasks/arc101_c

問題

N(偶数)頂点からなる木を成す無向グラフを考える。
2頂点ずつペアにしてN/2個の組を作り、それぞれの頂点間のパスを考える。
ペアの作り方のうち、N/2本のパスが全辺を最低1回は通るような組み合わせは何通りか。

解法

包除原理で解く。
辺集合Eのうち、絶対にパスが通過しない辺の集合をFとするペアの組み方をg(F)とする。
すると求める解はである。
g(F)は|F|+1頂点のペアの組み方なので、実際は辺の数のみで決まる。

• |F|+1が偶数の場合、|F|!!
• |F|+1が奇数の場合、0

よって、DFSで葉の頂点から、子頂点との辺を残す場合と減らす場合について、以下を順次更新すればO(N^2)で求められる。
dfs(v,n,o) := vを根とするsubtreeにおいて、vと連結する頂点数がnで、取り除く辺の偶奇がo(バイナリ値)であるような組み合わせの数

int N;
vector<int> E[5050];
ll G[5050];
int C[5050];
ll dp[5050][5050][2];
ll mo=1000000007;
ll tmp[5050][2]={};

void dfs(int cur,int pre) {
	C[cur]=1;
	dp[cur][1][0]=1;
	
	FORR(e,E[cur]) if(e!=pre) {
		int x,y;
		dfs(e,cur);
		ZERO(tmp);
		for(x=1;x<=C[cur];x++) {
			for(y=1;y<=C[e];y++) {
				// con
				(tmp[x+y][0] += dp[cur][x][0]*dp[e][y][0]+dp[cur][x][1]*dp[e][y][1])%=mo;
				(tmp[x+y][1] += dp[cur][x][0]*dp[e][y][1]+dp[cur][x][1]*dp[e][y][0])%=mo;
				// rem
				(tmp[x][1] += dp[cur][x][0]*dp[e][y][0]%mo*G[y]+dp[cur][x][1]*dp[e][y][1]%mo*G[y])%=mo;
				(tmp[x][0] += dp[cur][x][0]*dp[e][y][1]%mo*G[y]+dp[cur][x][1]*dp[e][y][0]%mo*G[y])%=mo;
			}
		}
		swap(tmp,dp[cur]);
		C[cur]+=C[e];
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	G[2]=1;
	for(i=3;i<=5030;i++) G[i]=G[i-2]*(i-1)%mo;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,-1);
	ll ret=0;
	for(i=1;i<=N;i++) {
		ret+=dp[0][i][0]*G[i]%mo;
		ret-=dp[0][i][1]*G[i]%mo;
	}
	cout<<(ret%mo+mo)%mo<<endl;
}

まとめ

包除原理だろうな、まではいいけどその先が詰めにくい。