ARC101E Ribbons on Tree

Description

给定一棵大小为 $n$ 的树，你需要给树上的点两两配对，对于一组对子 $(u,v)$ ，在树上将 $u\rightarrow v$ 的路径染色。定义一个配对方案合法当且仅当所有边都有颜色。
求方案数对 $10^9 + 7$ 取模。
$n\leq 5\times 10^3,2|n$

Solution

假设对于第 $i$ 条边而言，所有的给其染色的方案集合为 $A_i$ 。那么题目所求即为

$|\bigcap_{i=1}^{n} A_i|$

用容斥原理转化一下成了

$|\bigcap_{i=1}^{n} A_i| = \sum_{S\in [n]} (-1)^{|S|+1}|\bigcup_{i\in S} A_i| =\sum_{S\in [n]}(-1)^{|S|}|\bigcap_{i\in S} \overline{A_i}|$

其中 $\overline{A_i}$ 表示 $A_i$ 的补集，也就是所有不给第 $i$ 条边染色的方案数。

那么现在相当于我们钦定了一个边集不能染色，求染色方案数。
考虑如何计算。通过这个边集把树割成了若干个连通块，每个连通块方案数独立，并且内部可以任意连。
也就是求 $x$ 个点任意配对的方案数。假设某个连通块有 $x$ 个点，那么这个连通块的染色方案数为

$g(x) = 1\times 3\times 5\times \cdots \times (x-1)$

当然，如果 $x$ 是偶数才有解，奇数那必然是 $0$ 。
具体这个式子怎么来的可以这样考虑：每次先找到当前点集中的最小标号点，再任找一点与之匹配。

可以发现，钦定一个边集没有染色比起钦定了一个边集必须染色，求方案数要方便许多。

那么我们直接 DP 。设 f[i][j] 表示在 $i$ 子树内，$i$ 最后处于一个大小为 $j$ 的连通块，并且该连通块的贡献还未计算的带容斥系数的方案数之和。
考虑转移 按照 $p\rightarrow u$ 这条边是否断掉分成两种。

$f_{p,j+k}=\sum_{j}\sum_{k}f_{p,j}\times f_{u,k}\\ f_{p,j}=-\sum_{j}\sum_{k}f_{p,j}\times f_{u,k}\times g_k$

取负号是因为对于当前连通块而言，并上来的连通块必然要加一条边，而边的大小恰好决定正负性。
这里也很容易看出来我们在状态中不计算当前连通块的贡献的好处：方便向上延伸。毕竟连通块的贡献只有当知道了连通块的大小时才好计算。

如果在转移过程中割去了偶数条边，那么转移完这份贡献将不带负号，正好是容斥式子中所写的。所以我们初值设 $1$ 即可。

卡卡上界就可以做到 $\mathcal{O}(n^2)$ 了。

Code

const int N = 5e3 + 5, mod = 1e9 + 7;
using namespace std;
int n, num;
int head[N], to[N << 1], nt[N << 1];
int f[N][N], g[N], sz[N], tmp[N];
void Add(int x, int y){
    ++num, nt[num] = head[x], head[x] = num, to[num] = y;
    ++num, nt[num] = head[y], head[y] = num, to[num] = x;
}
void dp(int p, int fa){
    sz[p] = f[p][1] = 1;
    for(int i = head[p]; i; i = nt[i]){
        int v = to[i]; if(v == fa) continue;
        dp(v, p);
        memset(tmp, 0, sizeof tmp);
        for(int i = 1; i <= sz[p]; ++i)
        for(int j = 1; j <= sz[v]; ++j){
            (tmp[i] += mod - 1ll * f[p][i] * f[v][j] % mod * g[j] % mod) %= mod;
            (tmp[i + j] += 1ll * f[p][i] * f[v][j] % mod) %= mod;
        }
        sz[p] += sz[v];
        for(int i = 1; i <= sz[p]; ++i)
            f[p][i] = tmp[i];
    }
}
int main(){

    r(n);
    for(int i = 1, x, y; i < n; ++i)
        r(x, y), Add(x, y);
    g[0] = 1;
    for(int i = 2; i <= n; i += 2) 
        g[i] = 1ll * g[i - 2] * (i - 1) % mod;
    dp(1, 0);
    int ans = 0;
    for(int i = 2; i <= n; i += 2)
        (ans += 1ll * f[1][i] * g[i] % mod) %= mod;
    w(ans);
    return 0;
}