ARC101 E - Ribbons on Tree

AtCoder Regular Contest
問題

n(:偶数)頂点の木が与えられる
これらの頂点を端点を共有しないペアn/2組に分け、各ペアの2頂点間にリボンを張る
どの辺にも少なくとも1本のリボンが張られているようなペアの分け方は何通りあるか

2 <= n <= 5000

解法

f(S): Sのどの辺にもリボンが張られていないようなペアの分け方の個数
とすると、包除原理より答えは
Σ f(S) * (-1)^|S| (S: 与えられた木の辺の部分集合)
となる
ではf(S)は具体的にはどう求めれば良いか？

木からSの辺を全て取り除いて出来るグラフをGとする
このグラフは |S|+1 個の連結成分に分かれる
g(i): i番目の連結成分(サイズはk[i]とする)の各頂点をk[i]/2個のペアに分ける方法の個数
とすると、
k[i]が奇数のとき) g[i] = 0
k[i]が偶数のとき) g[i] = (k-1) * (k-3) * (k-5) * ... * 3 * 1
となり、f(S)は g[0] * g[1] * ... * g[|S|] である
あとは各Sについてこれらを足し合わせていけば解けるけど、Sを全通り (2^(n-1)通り) 試すわけにはいかないからうまく状態をまとめて計算する必要がある

dp[v][x][p]: 頂点vを根とする部分木において、vを含む連結成分の頂点数がxで、部分木内で取り除いた辺の本数の偶奇がpとなるようなペア分けの仕方の個数
これを木の葉から根に向かって更新していけばいい
頂点0を木の根とすると答えは Σ (dp[0][i][0] - dp[0][i][1]) (1 <= i <= n) となる

部分木同士のdpをマージするとき、xの値として[0,n]の範囲を毎回見ているとO(n^2)かかり、マージはn-1回行われるからトータルでO(n^3)になってしまう
でも実際はサイズがXの部分木のdpではxの上限はXまでで十分
よっていまマージしようとしている2個の部分木それぞれの頂点数がXとYであるとするとO(XY)でマージできる
こうするとトータルでO(n^2)になる
これは木dpではめちゃくちゃよく使うテクニックらしい

#define int long long

int n, x, y, dp[5050][5050][2], dp2[5050][2], sz[5050], g[5050], res;
vector<int> e[5050];

void rec(int v, int p) {
	sz[v] = 1, dp[v][1][0] = 1;
	each(i,e[v]) if (i!=p) {
		rec(i,v);
		memset(dp2,0,sizeof(dp2));
		reps(x,1,sz[v]+1) reps(y,1,sz[i]+1) {
			// v-i間の辺を取り除く場合
			(dp2[x][0] += dp[v][x][0]*dp[i][y][1]%mod*g[y] + dp[v][x][1]*dp[i][y][0]%mod*g[y]) %= mod;
			(dp2[x][1] += dp[v][x][0]*dp[i][y][0]%mod*g[y] + dp[v][x][1]*dp[i][y][1]%mod*g[y]) %= mod;
			// 取り除かない場合
			(dp2[x+y][0] += dp[v][x][0]*dp[i][y][0] + dp[v][x][1]*dp[i][y][1]) %= mod;
			(dp2[x+y][1] += dp[v][x][0]*dp[i][y][1] + dp[v][x][1]*dp[i][y][0]) %= mod;
		}
		swap(dp[v],dp2);
		sz[v] += sz[i];
	}
}

signed main() {
	g[2] = 1;
	reps(i,4,5050) g[i] = g[i-2]*(i-1) %mod;
	cin >> n;
	rep(i,n-1) {
		cin >> x >> y;
		x--, y--;
		e[x].push_back(y), e[y].push_back(x);
	}
	rec(0,-1);
	reps(i,1,n+1) (res += (dp[0][i][0]-dp[0][i][1])*g[i]) %= mod;
	(res += mod) %= mod;
	cout << res << endl;
}