Visits: 300

ARC101E Ribbons on Tree

题意

• 给定一棵 $n$ 个点的树，保证 $n$ 为偶数。
• 将 $n$ 个点分成 $\frac n2$ 个无序点对。
• 对于每个点对，将树上两点之间的最短路径上的边染色。
• 问有多少种方案使得每条边都被染色。
• $n \le 5 \times 10^3$，答案对 $10^9+7$ 取模。

题解

考虑容斥，设 $f(S)$ 表示强制不覆盖边集 $S$ 中的边的方案数，则答案为 $\sum_{S \subseteq E} (-1)^{|S|} f(S)$。

考虑 $f(S)$ 如何计算，设 $S$ 中的边割掉后将树分成了大小为 $a_{1},a_2,\cdots,a_t$ 这 $t$ 个连通块，则 $f(S) = \prod_{t=1}^t \left[2 | a_i\right]\left(a_i-1\right)!!$，其中 $x!!$ 表示 $x(x-2)(x-4)\cdots$。

考虑树形 DP，设 $f_{i,j}$ 表示考虑 $i$ 的子树，割掉若干条边后 $i$ 所在的连通块大小为 $j$，不包含 $i$ 所在的连通块的贡献总和。

转移就是树上背包，时间复杂度 $\mathcal O(n^2)$。

代码

const int N = 5e3 + 7;
int n, s[N];
vi e[N];
modint p[N], f[N][N], ans;

void dfs(int x, int fa) {
    f[x][1] = s[x] = 1;
    for (int y : e[x])
        if (y != fa) {
            dfs(y, x);
            for (int i = s[x]; i; i--) {
                modint w = 0;
                for (int j = s[y]; j; j--)
                    f[x][i+j] += f[x][i] * f[y][j], w -= p[j] * f[y][j];
                f[x][i] *= w;
            }
            s[x] += s[y];
        }
}

int main() {
    rd(n);
    p[2] = 1;
    for (int i = 4; i <= n; i += 2) p[i] = p[i-2] * (i - 1);
    for (int i = 1, x, y; i < n; i++) rd(x, y), e[x].pb(y), e[y].pb(x);
    dfs(1, 0);
    for (int i = 1; i <= n; i++) ans += p[i] * f[1][i];
    print(ans);
    return 0;
}