ARC101 E Ribbons on Tree

問題文

https://beta.atcoder.jp/contests/arc101/tasks/arc101_c

 

どの辺にも少なくとも1本のリボンが張られるようなペアの分け方を直接数えるのは難しい.「f(S)=Sに含まれる辺には1本もリボンが張られないようなペアの分け方」とすると包除原理より答えはΣ(-1)^|S|f(S)で求まるので,これを使って上手く求めたい.

Sに含まれる辺に1本もリボンが張られないペアの分け方はどんなものだろうか.これは,木からSに含まれる辺を取りのぞいて|S|+1個の連結成分に分割し,各連結成分内でペアを作るような分け方である.

ではx個のものがあって,それらをペアに分けるとき,異なる分け方は何通りあるだろうか.

これはxが奇数のとき0通り,xが偶数のときは(x-1)・(x-3)・...・1通りである.

これで計算量を無視すればとけたのだが,今回の場合,Sを全て試すことは当然できないので工夫が必要(本番ではここから進めなかった).

包除原理の高速化には色々なパターンがあるが,今回の場合は|S|の偶奇で分けて,|S|が偶数であるとき,|S|が奇数であるときそれぞれについてΣf(S)を求めればいい.

これで重要なのがSの偶奇と根が含まれる連結成分の大きさ(その連結成分をペアに分ける方法が何通りか計算するため)だけになったので,「dp[v][s][p]=頂点vが含まれる連結成分の大きさがsで,頂点vのサブツリー内で取りのぞいた辺の数の偶奇がpであるときのペアの分け方(ただし頂点vが含まれる連結成分はまだペアに分けない)」として木DPをすれば|S|が偶数であるとき,奇数であるときそれぞれについてΣf(S)が求まる.

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
vector<int> G[5000];
ll dp[5000][5001][2];
ll dp2[2][5001][2];
int subtree[5000];
ll fact[5001];
void calc(int v, int p) {
    subtree[v] = 1;
    for (int to : G[v]) {
        if (to == p) continue;
        calc(to, v);
        subtree[v] += subtree[to];
    }
}
void solve(int v, int p) {
    int size = 1;
    int idx = 0;
    for (int to : G[v]) {
        if (to == p) continue;
        solve(to, v);
    }
    memset(dp2, 0, sizeof(dp2));
    dp2[0][1][0] = 1;
    for (int to : G[v]) {
        if (to == p) continue;
        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= subtree[to]; j++) {
                ll add = (dp2[idx][i][0] * dp[to][j][0]) % MOD;
                (add += (dp2[idx][i][1] * dp[to][j][1]) % MOD) %= MOD;
                (dp2[idx ^ 1][i][1] += (add*fact[j]) % MOD) %= MOD;
                add = (dp2[idx][i][0] * dp[to][j][1]) % MOD;
                (add += (dp2[idx][i][1] * dp[to][j][0]) % MOD) %= MOD;
                (dp2[idx ^ 1][i][0] += (add*fact[j]) % MOD) %= MOD;
                (dp2[idx ^ 1][i + j][0] += (dp2[idx][i][0] * dp[to][j][0]) % MOD) %= MOD;
                (dp2[idx ^ 1][i + j][0] += (dp2[idx][i][1] * dp[to][j][1]) % MOD) %= MOD;
                (dp2[idx ^ 1][i + j][1] += (dp2[idx][i][1] * dp[to][j][0]) % MOD) %= MOD;
                (dp2[idx ^ 1][i + j][1] += (dp2[idx][i][0] * dp[to][j][1]) % MOD) %= MOD;
            }
        }
        for (int i = 1; i <= size; i++) dp2[idx][i][0] = dp2[idx][i][1] = 0;
        size += subtree[to];
        idx ^= 1;
    }
    for (int i = 1; i <= size; i++) {
        dp[v][i][0] = dp2[idx][i][0];
        dp[v][i][1] = dp2[idx][i][1];
    }
}
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    fact[2] = 1;
    for (int i = 4; i <= N; i += 2) {
        fact[i] = (fact[i - 2] * (i - 1)) % MOD;
    }
    calc(0, -1);
    solve(0, -1);
    ll ans = 0;
    for (int i = 1; i <= subtree[0]; i++) {
        (ans += (dp[0][i][0] * fact[i]) % MOD) %= MOD;
        (ans += ((MOD - dp[0][i][1])*fact[i]) % MOD) %= MOD;
    }
    cout << ans << endl;
}