ARC101C 题解

· · 题解

首先可以很容易想到一个 \mathcal{O}(n^3) 的 dp，在子树归并的同时枚举这次匹配的点对数，然后转移

发现这个 dp 不太好进行优化，考虑换一个思路去做

题目中要求的是恰好所有边都被经过，即恰好有 0 条边不被经过，不妨考虑子集反演，钦定集合 S\in E，F(S) 表示集合 S 中的边都不被经过的方案数，那我们最后要求的答案就变成了

\sum(-1)^{|S|}F(S)

考虑如何求 F(S)，我们将这些边都断掉，会形成 |S|-1 个联通块，因为定义中并没有钦定剩下的边一定被经过，所以直接在同一个联通块里随便选两个点连就行了，要求的就是是这 |S|-1 个联通块中，每个联通块里的每两个点匹配且要完全匹配的方案数，显然这 |S|-1 个联通块是独立的，可以分开求

定义 g(n) 表示一个联通块里有 n 个点，两两随便匹配的方案数，因为点对是无序的，点对与点对之间也是无序的，所以我们直接钦定它有序，对每个点选个点匹配就行，直接可以得出式子

g(n)=[n\equiv 0\pmod2](n-1)(n-3)......3\times 1

所以对于一个 F(S)，其实就是它分成的若干个联通块的 g(n) 乘起来

接下来我们可以考虑继续在树上 dp 来解决这个问题

定义 f[i][j] 表示以 i 为根的子树，i 所在的联通块大小为 j 的方案数

然后子树归并，转移是决策 u 所在的联通块是否与 v 所在的联通块合并就行了

特别的，根据定义和转移，我们发现 f[i][0] 其实就是不与上面的联通块合并，即断掉了 fa[i] 与 i 之间的边，因为断边集合 S 大小增加了 1，需要乘上个 -1，而且现在一个联通块考虑完了，同时在乘上一个 g(j) 即可，即

f[u][0]=-1\times \sum_{j=1}^{size[u]}f[u][j]\times g(j)

最后特殊考虑一下根节点，因为它没有 fa，所以无边可断，不需要乘 -1，最后答案即为 -1\times f[1][0]

因为只剩下了子树归并，所以复杂度是 \mathcal{O}(n^2) 的

\mathcal{Code} 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

const int maxn = 5e3 + 50, INF = 0x3f3f3f3f, mod = 1e9 + 7;

inline int read () {
    register int x = 0, w = 1;
    register char ch = getchar ();
    for (; ch < '0' || ch > '9'; ch = getchar ()) if (ch == '-') w = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar ()) x = x * 10 + ch - '0';
    return x * w;
}

inline int addmod (register int a, register int b) {
    return a += b, a >= mod ? a - mod : a;
}

inline ll mulmod (register ll a, register int b) {
    return a *= b, a >= mod ? a % mod : a;
}

int n;

struct Edge {
    int to, next;
} e[maxn << 1];

int tot, head[maxn];

inline void Add (register int u, register int v) {
    e[++ tot].to = v;
    e[tot].next = head[u];
    head[u] = tot;
}

int siz[maxn], f[maxn][maxn], g[maxn], p[maxn];

inline void Init () {
    g[0] = 1;
    for (register int i = 2; i <= n; i += 2) 
        g[i] = mulmod (g[i - 2], i - 1);
}

inline void DFS (register int u, register int fa) {
    siz[u] = 1, f[u][1] = 1;
    for (register int i = head[u]; i; i = e[i].next) {
        register int v = e[i].to;
        if (v == fa) continue;
        DFS (v, u);
        for (register int j = 1; j <= siz[u] + siz[v]; j ++) p[j] = 0;
        for (register int j = 1; j <= siz[u]; j ++) 
            for (register int k = 0; k <= siz[v]; k ++) 
                p[j + k] = addmod (p[j + k], mulmod (f[u][j], f[v][k]));
        for (register int j = 1; j <= siz[u] + siz[v]; j ++) f[u][j] = p[j];
        siz[u] += siz[v];
    }
    for (register int j = 1; j <= siz[u]; j ++) 
        f[u][0] = addmod (f[u][0], mulmod (f[u][j], g[j]));
    f[u][0] = mod - f[u][0];
}

int main () {
    n = read(), Init ();
    for (register int i = 1, u, v; i < n; i ++)
        u = read(), v = read(), Add (u, v), Add (v, u);
    DFS (1, 0), printf ("%d\n", mod - f[1][0]);
    return 0;
}