これ系苦手…。
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; }
まとめ
包除原理だろうな、まではいいけどその先が詰めにくい。