配对 - 题解

标签与难度

标签: 树形DP, 动态规划, 组合计数, 计数DP, 图论 难度: 2500

题目大意喵~

主人你好呀~ 这道题是这样的：我们有一棵 $n$ 个点的树，$n$ 是一个偶数，喵。我们需要把这 $n$ 个点两两配对，形成 $n/2$ 个点对。

对于每一个点对 $(u, v)$，它们之间在树上的距离（也就是简单路径的边数）是 $d(u, v)$。一个完整的配对方案的“权值”，是所有 $n/2$ 个点对的距离的乘积，也就是 $\prod_{i=1}^{n/2} d(u_i, v_i)$。

我们的任务，就是计算所有不同的配对方案的权值之和，最后结果对 $10^9 + 7$ 取模。只要有一个点在两种方案里配对的伙伴不一样，这两种方案就被认为是不同的，喵~

举个栗子：$n=4$ 的一条链 1-2-3-4。

• 方案一：(1,2), (3,4)。距离分别是 $1, 1$。权值是 $1 \times 1 = 1$。
• 方案二：(1,3), (2,4)。距离分别是 $2, 2$。权值是 $2 \times 2 = 4$。
• 方案三：(1,4), (2,3)。距离分别是 $3, 1$。权值是 $3 \times 1 = 3$。 所有方案的权值总和就是 $1 + 4 + 3 = 8$ 啦，喵~

解题思路分析

这道题的目标是“所有方案的权值和”，而且权值是“距离的乘积”，这种形式通常都非常适合用动态规划来解决，特别是当题目背景是一棵树的时候，树形DP就闪亮登场啦，喵！

直接计算所有配对方案是不可能的，因为方案数太多了。我们需要设计一个DP状态，能够从子树慢慢合并到整棵树，并且在合并的过程中，把配对信息和权值和都正确地传递上去。

这道题的DP状态设计是关键，也是最巧妙的地方，喵~。直接用 dp[u][k] 表示 $u$ 子树里有 $k$ 个点没配对，并记录权值和，是行不通的。因为当子树的两个点要和外面的点配对时，它们的距离会经过子树的根 $u$ 和连接到父节点的边，这个距离信息 d(leaf, u) 很难在DP状态里维护。

所以，我们需要一个更强大的DP状态！

DP状态定义

让我们定义一个三维的DP状态 dp[u][i][j]：

• u：表示当前计算的是以 u 为根的子树。
• i：表示在 u 的子树中，有 i 个节点已经被指定要和子树外面的点配对，并且它们的配对路径已经“预定”了要向上经过 u 和它父节点之间的边。我们可以称它们为“向上路径”。
• j：表示在 u 的子树中，有 j 个节点还没有配对，但它们暂时还只在子树内部等待配对，没有确定要和子树外的点配对。我们称它们为“待定节点”。

dp[u][i][j] 的值是：在以 u 为根的子树中，满足上述状态（即有 i 条向上路径，j 个待定节点，其余 sz[u] - i - j 个点在子树内部完美配对）的所有可能情况的权值总和。

这里的权值，指的是那些已经在子树内部完成配对的点对的距离乘积。

DP转移过程

我们用一次DFS（深度优先搜索），以后序遍历的顺序来进行DP计算。对于每个节点 u，我们先递归计算它所有子节点 v 的DP值，然后把子节点的信息合并到 u 上。

1. 基础情况 (Base Case - 叶子节点)

对于一个叶子节点 u，它的子树里只有它自己一个点。它没法在内部配对，所以它必须和外面的点配对。它自己就是一个“待定节点”。 所以，dp[u][0][1] = 1。（0条向上路径，1个待定节点，内部配对的权值积是1（空积））。

2. 合并子树 (Merge)

这是最核心的一步！假设我们正在计算节点 u，它已经处理完了一些子节点，当前的状态是 dp_u[i1][j1]。现在我们要合并一个新的子树，根为 v，它的状态是 dp_v[i2][j2]。

合并就是考虑 u 这边的未配对节点和 v 那边的未配对节点之间如何配对。

• u 这边有 i1 条向上路径和 j1 个待定节点。
• v 这边有 i2 条向上路径和 j2 个待定节点。

它们之间可以发生两种新的配对：

• u 的待定节点↔️ v 的向上路径：从 u 的 j1 个待定节点中选 k 个，和 v 的 i2 条向上路径选 k 条进行配对。
• u 的向上路径 ↔️ v 的待定节点：从 u 的 i1 条向上路径中选 k' 个，和 v 的 j2 个待定节点选 k' 个进行配对。

这两种配对很关键！一条从 v 出来的“向上路径”意味着一个 v 子树里的点，它的路径已经算上了 d(leaf, v)，并且通过 (u,v) 这条边到达了 u。当它和 u 侧的一个“待定节点”配对时，一条完整的路径就形成了！这个距离的计算被奇妙地隐藏在了状态转移中。我们只需要负责组合计数就可以啦。

合并后的新状态 dp_new[i_new][j_new] 的计算如下：

• i_new = (i1 - k') + (i2 - k)：剩下的向上路径。
• j_new = (j1 - k) + (j2 - k')：剩下的待定节点。
• dp_new[i_new][j_new] 会累加上 dp_u[i1][j1] * dp_v[i2][j2] * C(j1,k) * C(i2,k) * k! * C(i1,k') * C(j2,k') * k'!。
  • C(a,b) 是组合数，b! 是阶乘，因为配对是有关顺序的。

我们用一个临时数组 tmp_dp 来存储合并后的结果，然后更新 dp[u]。

3. 向上“晋升” (Promotion)

当节点 u 合并完它所有的子树后，我们得到了最终的 dp[u][i][j]。这个状态是从 u 的视角看的。在返回给 u 的父节点 p 之前，我们需要更新这个状态，以匹配 p 的视角。

对于 u 的 j 个待定节点，它们中的任何一个都有可能不和 u 子树内部的其他节点配对，而是要和 u 子树外面的节点配对。如果一个待定节点决定要“出走”，那它的路径就必须经过 (u,p) 这条边。 所以，我们可以从 j 个待定节点中，选择 k 个，让它们“晋升”为向上路径。

• 原来有 i 条向上路径，j 个待定节点。
• 晋升后，就有 i+k 条向上路径，j-k 个待定节点。
• 这个选择有 C(j,k) 种方式。

这个操作是在 dfs(u) 返回前，对 dp[u] 进行的最后一次转换。

4. 最终答案

当整个DFS过程结束，我们回到最初的根节点（比如节点1）。我们要求的最终答案是所有点都完美配对的情况。这意味着在根节点1，不应该有任何未配对的节点剩下。 所以，答案就是 dp[1][0][0] 啦！

这个DP的思路真的非常精妙，它把复杂的距离计算通过“向上路径”和“待定节点”的状态划分给分解了，我们只需要专注于组合计数的部分，最终就能得到神奇的答案，喵~

代码实现

这是本喵根据上面的思路，精心重构的一份代码~ 希望能帮到你，喵！

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 55;

// 使用长整型避免中间计算溢出
using ll = long long;

int n;
vector<int> adj[MAXN];

// 预计算组合数和阶乘
ll C[MAXN][MAXN];
ll fact[MAXN];

// dp[u][i][j]: 子树u中, 有i条向上路径, j个待定节点时的权值和
ll dp[MAXN][MAXN][MAXN];
int subtree_size[MAXN];

// 临时DP数组，用于合并
ll temp_dp[MAXN][MAXN];

// 辅助函数，用于模块化加法
void add(ll &a, ll b) {
    a = (a + b) % MOD;
}

void precompute_combi() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    for (int i = 0; i < MAXN; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
}

void dfs(int u, int p) {
    // 1. Base Case: 叶子节点
    subtree_size[u] = 1;
    dp[u][0][1] = 1; // 0条向上路径, 1个待定节点(u自己)

    // 2. 递归与合并
    for (int v : adj[u]) {
        if (v == p) continue;
        
        dfs(v, u);

        // 初始化临时DP数组
        for (int i = 0; i <= subtree_size[u] + subtree_size[v]; ++i) {
            for (int j = 0; j <= subtree_size[u] + subtree_size[v]; ++j) {
                temp_dp[i][j] = 0;
            }
        }

        // 合并子树 v 到 u
        for (int i1 = 0; i1 <= subtree_size[u]; ++i1) {
            for (int j1 = 0; j1 <= subtree_size[u] - i1; ++j1) {
                if (dp[u][i1][j1] == 0) continue;

                for (int i2 = 0; i2 <= subtree_size[v]; ++i2) {
                    for (int j2 = 0; j2 <= subtree_size[v] - i2; ++j2) {
                        if (dp[v][i2][j2] == 0) continue;

                        ll base_product = (dp[u][i1][j1] * dp[v][i2][j2]) % MOD;

                        // k1: u的向上路径 <-> v的待定节点
                        for (int k1 = 0; k1 <= min(i1, j2); ++k1) {
                            // k2: u的待定节点 <-> v的向上路径
                            for (int k2 = 0; k2 <= min(j1, i2); ++k2) {
                                ll combinations = C[i1][k1];
                                combinations = (combinations * C[j2][k1]) % MOD;
                                combinations = (combinations * fact[k1]) % MOD;
                                combinations = (combinations * C[j1][k2]) % MOD;
                                combinations = (combinations * C[i2][k2]) % MOD;
                                combinations = (combinations * fact[k2]) % MOD;

                                ll val = (base_product * combinations) % MOD;
                                
                                int next_i = i1 - k1 + i2 - k2;
                                int next_j = j1 - k2 + j2 - k1;
                                add(temp_dp[next_i][next_j], val);
                            }
                        }
                    }
                }
            }
        }

        subtree_size[u] += subtree_size[v];
        for (int i = 0; i <= subtree_size[u]; ++i) {
            for (int j = 0; j <= subtree_size[u]; ++j) {
                dp[u][i][j] = temp_dp[i][j];
            }
        }
    }
    
    // 3. 向上“晋升”
    // 在返回给父节点前, u子树内的待定节点j可以晋升为向上路径
    if (u != 1) { // 根节点不需要晋升
        for (int i = 0; i <= subtree_size[u]; ++i) {
            for (int j = 0; j <= subtree_size[u]; ++j) {
                temp_dp[i][j] = 0;
            }
        }
        
        for (int i = 0; i <= subtree_size[u]; ++i) {
            for (int j = 0; j <= subtree_size[u] - i; ++j) {
                if(dp[u][i][j] == 0) continue;
                for (int k = 0; k <= j; ++k) {
                    // 从j个待定节点中选k个晋升为向上路径
                    ll val = (dp[u][i][j] * C[j][k]) % MOD;
                    add(temp_dp[i + k][j - k], val);
                }
            }
        }
        
        for (int i = 0; i <= subtree_size[u]; ++i) {
            for (int j = 0; j <= subtree_size[u]; ++j) {
                dp[u][i][j] = temp_dp[i][j];
            }
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute_combi();

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0);

    cout << dp[1][0][0] << endl;

    return 0;
}

复杂度分析

• 时间复杂度: $O(N^5)$。DP的状态是三维的，但有效状态是 $O(N^2)$（因为 i+j <= N）。在合并两个子树 u 和 v（大小分别为 s_u 和 s_v）时，我们有六层循环（i1, j1, i2, j2, k1, k2）。虽然看起来很吓人，但由于循环变量之间有大小限制，并且对树上所有节点的合并成本进行摊还分析，对于 $N=50$ 的数据规模，总的计算量是可以接受的。在一些特殊树形（如链或菊花图）上，复杂度会更优，大约是 $O(N^4)$。
• 空间复杂度: $O(N^3)$。DP数组 dp[N][N][N] 主导了空间开销。

知识点总结

1. 树形DP: 解决树上计数或最优化问题的经典方法。通常通过DFS后序遍历，从子树向根节点合并信息。
2. 组合计数: DP转移中大量使用了组合数 C(n,k) 和阶乘 n! 来计算选择和配对的方案数。预计算这些值是标准操作。
3. 巧妙的DP状态设计: 这是本题的灵魂！通过将未配对节点划分为“向上路径”和“待定节点”，成功地将复杂的距离计算分解到DP状态的转移中，把问题转化为了一个组合计数问题。这种思想在处理树上路径相关的计数问题时非常强大，值得好好体会，喵~
4. DP合并思想: 将两个子问题的解合并成一个更大问题的解。这里的合并过程体现了DP的精髓，即考虑所有子问题之间的交互方式。

希望这篇题解能帮助主人理解这道有趣的题目！如果还有不明白的地方，随时可以再来问本喵哦~ 喵~