https://beta.atcoder.jp/contests/arc101/tasks/arc101_c
解法
https://beta.atcoder.jp/contests/arc101/submissions/3082593
求められる手法が多いので、そちらを学習してからの方がオススメ。
徐々に計算量を減らしていくのだが、包除原理を前提に考えないと終わる。
包除原理できるように木DPを考える。
dp[cu][ngedge][cnt] := 頂点cuの部分木で覆われていない辺がngedge以上であり、覆われてないかもしれない辺でcnt個頂点cuとつながっているときの組み合わせ数
どういうDPが分かりづらいが、公式解説動画を見てほしい。
公式解説動画で紹介されているDPとは順番とかちょっと違うので注意。
さて、このままだと計算量がやばいので、まずはDPを少し改善しよう。
「偶奇で更に圧縮するテク」を使おう。
最終的に答えを集計するときはngedgeの偶奇を見て足すか引くかなので、ngedgeの偶奇しか集計に使わない。
そして、ngedgeの実際の個数を使って組合せ計算をすることがないので偶奇だけに圧縮しても問題無い。
圧縮することで状態がO(N^3)からO(N^2)に減らすことができる。
これで木DPするが、今までのDPと子供のDPのマージも少し注意が必要。
まず、普通に2つの頂点でのDPをマージしようとすると、全てのマージでO(N)かかってしまいそう。
ここで「二乗の木DP」を使う。
DPの添字の中でcntはNまで用意しなくても、部分木の個数分で良い。
マージも同様にNまでやらなくても部分木の個数分更新で使えばいい。
これを丁寧にやるとならしO(N)になる。
更新式も複雑なのでマージ関数も少し細かく説明しておく。
comb[cnt] := 頂点数がcntの時のマッチングの組み合わせ数（この前のyukicoderで使った）
// dp[id0]とdp[id1]をマージしてdp[id0]に入れる void merge(int id0, int id1) { int sz0 = dp[id0][0].size(); // cntが0～sz0-1まで対応 int sz1 = dp[id1][0].size(); // cntが0～sz1-1まで対応 vector<vector<mint>> pd(2, vector<mint>(sz0 + sz1 - 1)); // 作られるcntは0～sz0+sz1-2 rep(c0, 0, sz0) rep(p0, 0, 2) rep(c1, 0, sz1) rep(p1, 0, 2) { // dp[id0][p0][c0]とdp[id1][p1][c1]をマージしていく pd[(p0 + p1) % 2][c0 + c1] += dp[id0][p0][c0] * dp[id1][p1][c1]; // 頂点id0と頂点id1を普通に接続する（ngedgeは変化しない） if (c1 % 2 == 0) pd[(p0 + p1 + 1) % 2][c0] += dp[id0][p0][c0] * dp[id1][p1][c1] * comb[c1]; // 頂点id0と頂点id1を接続しない（ngedgeが+1される） // ここで注意なのだが、接続しないとid1側が連結成分になるので、ちゃんとその中での // ペアも計算しないと行けない。ちゃんとペアが作れるためには個数が偶数である必要があるので、 // c1%2==0の場合だけ行える。 // comb[c1]は頂点数がc1の時のマッチングの組合せ } swap(dp[id0], pd); // 新しいdpに入れ替える }
大変だがテクを組み合わせるとAC
int N; vector<int> E[5010]; //--------------------------------------------------------------------------------------------------- mint comb[5010]; vector<vector<mint>> dp[5010]; void merge(int id0, int id1) { int sz0 = dp[id0][0].size(); int sz1 = dp[id1][0].size(); vector<vector<mint>> pd(2, vector<mint>(sz0 + sz1 - 1)); rep(c0, 0, sz0) rep(p0, 0, 2) rep(c1, 0, sz1) rep(p1, 0, 2) { pd[(p0 + p1) % 2][c0 + c1] += dp[id0][p0][c0] * dp[id1][p1][c1]; if (c1 % 2 == 0) pd[(p0 + p1 + 1) % 2][c0] += dp[id0][p0][c0] * dp[id1][p1][c1] * comb[c1]; } swap(dp[id0], pd); } void dfs(int cu, int pa = -1) { dp[cu].push_back({ 0, 1 }); // dp[cu][0] := 頂点cuの部分木で使ってない辺が0本以上 dp[cu].push_back({ 0, 0 }); // dp[cu][1] := 頂点cuの部分木で使ってない辺が1本以上 fore(to, E[cu]) if (to != pa) { dfs(to, cu); merge(cu, to); //dp[cu] = dp[cu] + dp[to] } } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } rep(i, 0, 5010) if (i % 2 == 0) { comb[i] = 1; int x = i - 1; while (1 < x) comb[i] *= mint(x), x -= 2; } dfs(0); mint ans = 0; rep(c, 0, dp[0][0].size()) if (c % 2 == 0) ans += dp[0][0][c] * comb[c]; rep(c, 0, dp[0][0].size()) if (c % 2 == 0) ans -= dp[0][1][c] * comb[c]; cout << ans << endl; }
