D. Maximum Distributed Tree - 题解

比赛与标签

比赛: Codeforces Round 665 (Div. 2) 标签: dfs and similar, dp, greedy, implementation, math, number theory, sortings, trees 难度: *1800

题目大意喵~

主人，这道题是这样的呐：

我们拿到了一棵有 n 个节点的树。我们的任务是给这棵树的 n-1 条边分别赋予一个正整数权重。这些权重需要满足三个条件：

1. 所有 n-1 个权重的乘积必须等于一个给定的数 k。
2. 在所有权重中，数字 1 的数量要尽可能少。
3. 我们要最大化一个叫做“分布指数”的值。

这个“分布指数”是树上所有节点对 (i, j) 之间简单路径的权重之和的总和。也就是说，把任意两个点之间路径上的边权加起来，再把所有这些路径和加起来，得到的那个超大的数就是分布指数啦！

因为 k 可能非常大，题目会直接给我们 k 的所有质因数。最后的结果要对 10^9 + 7 取模哦！

解题思路大揭秘！

这道题看起来有点复杂，但别怕，跟着我的思路一步步来，就会变得清晰起来喵~

关键的第一步：转化目标函数

我们想最大化的值是 Σ f(u,v)，也就是所有点对路径和的总和。直接去枚举所有点对 (u, v) 肯定是行不通的，太慢啦！

这时候，我们就要换个角度思考问题，喵~ 与其关心每个“点对”，不如我们来关心每一条“边”对总和的贡献是多少？

边的贡献是多少呢？

想象一下，我们随便拿起一把剪刀，把树上的一条边 e 剪断。会发生什么呢？这棵树立刻就分成了两个连通块（也就是两棵小树）！

假设其中一个连-通-块有 s 个节点，那另一个肯定就有 n-s 个节点，对吧？

现在考虑任意一条路径，如果它的起点在第一个连通块，终点在第二个连通块，那么这条路径是不是必须经过我们刚刚剪断的那条边 e 呢？是的说！

那么，这样的路径一共有多少条呢？从 s 个节点里选一个起点，从 n-s 个节点里选一个终点，总共有 s * (n-s) 种组合。这意味着，边 e 的权重 w(e) 会在最终的总和里被加 s * (n-s) 次！

所以，我们的总分布指数就可以写成：Σ (w_i * c_i)，其中 w_i 是第 i 条边的权重，c_i 是第 i 条边的贡献次数（也就是 s * (n-s)）。

贪心大法好！

我们的目标是最大化 Σ (w_i * c_i)。这是一个经典的贪心问题！要想让乘积之和最大，我们应该把最大的权重 w_i 分配给贡献次数最多的边 c_i，第二大的权重分配给贡献次数第二多的边，以此类推。这就是著名的排序不等式思想，喵~

所以，我们的策略就明确了：

1. 计算出每条边的贡献次数 c_i。
2. 根据 k 的质因数，构造出 n-1 个边的权重 w_i。
3. 将 c_i 和 w_i 两个列表都从大到小排序。
4. 将排序后的列表对应相乘再求和，就是我们的最大答案啦！

如何计算贡献和分配权重？

1. 计算贡献次数 c_i 我们可以随便选一个节点当根（比如节点0），然后做一次深度优先搜索（DFS）。在DFS的过程中，我们可以计算出以每个节点为根的子树大小 size[u]。 对于一条连接节点 u 和其父节点 p 的边，它分割出的两个连通块就是 u 的子树和树的其余部分。所以，这条边的贡献次数就是 size[u] * (n - size[u])。我们对所有非根节点计算这个值，就能得到所有 n-1 条边的贡献次数了。

2. 分配权重 w_i 我们有 m 个质因数，需要分配给 n-1 条边，并且要让 1 的数量最少。

• 情况一：质因数不够 (m < n-1) 如果我们只有 m 个质因数，但有 n-1 条边，那么为了满足乘积为 k，必然有 (n-1) - m 条边的权重得是 1。为了让 1 的数量最少，我们就让 m 条边分别取一个质因数作为权重，剩下的边权重为 1。

• 情况二：质因数充足 (m >= n-1) 当质因数比边多的时候，我们可以让每条边都有一个大于 1 的权重！为了让我们的贪心策略效果最好（即创造出尽可能大的权重），我们应该把最大的几个质因数“捆绑”在一起。 具体做法是：将 m 个质因数从大到小排序。我们取出前 m - (n-1) + 1 个最大的质因数，把它们全部乘起来，作为第一个权重。剩下的质因数，每个单独作为一个权重。这样我们就得到了 1 + (m - (m - n + 2)) = n-1 个权重，完美！

把这两步得到的贡献次数列表和权重列表分别排序，然后配对相乘求和，就得到最终答案啦！别忘了每一步计算都要取模哦，喵~

代码实现喵~

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

const long long mod = 1000000007;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<vector<int>> adj(n);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            u--; v--; // 转换为0-indexed
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        // --- Step 1: 计算每条边的贡献次数 ---
        // 使用非递归的DFS来计算子树大小，避免栈溢出
        vector<int> parent(n, -1);
        vector<int> size_arr(n, 1); // size_arr[i] 表示以i为根的子树大小
        vector<int> order; // 存储节点的后序遍历顺序
        stack<int> st;

        st.push(0); // 从节点0开始遍历
        parent[0] = -1;

        // 第一次遍历，建立父子关系和遍历顺序
        while (!st.empty()) {
            int u = st.top();
            st.pop();
            order.push_back(u);
            for (int v : adj[u]) {
                if (v == parent[u]) continue;
                parent[v] = u;
                st.push(v);
            }
        }

        // 后序遍历（反转order），从叶子节点向上计算子树大小
        reverse(order.begin(), order.end());
        for (int u : order) {
            // 这个循环其实只会执行一次，因为parent[u]只有一个
            for (int v : adj[u]) {
                if (v == parent[u]) continue;
                // 将子节点的大小加到父节点上
                size_arr[u] += size_arr[v];
            }
        }

        // 计算每条边的贡献次数 = size * (n - size)
        vector<long long> contrib;
        for (int i = 1; i < n; i++) { // 遍历所有非根节点，计算其与父节点连接的边的贡献
            contrib.push_back((long long)size_arr[i] * (n - size_arr[i]));
        }

        // --- Step 2: 构造边的权重 ---
        int m;
        cin >> m;
        vector<long long> primes(m);
        for (int i = 0; i < m; i++) {
            cin >> primes[i];
        }

        // 将质因数从大到小排序，方便构造最大的权重
        sort(primes.rbegin(), primes.rend());

        vector<long long> weights;
        if (m <= n - 1) { // 情况一：质因数不够
            weights = primes;
            weights.resize(n - 1, 1); // 不足的用1填充
        } else { // 情况二：质因数充足
            long long prod = 1;
            int num_first = m - (n - 1) + 1; // 需要合并的质因数数量
            // 将最大的几个质因数相乘，构造一个超大权重
            for (int i = 0; i < num_first; i++) {
                prod = (prod * primes[i]) % mod;
            }
            weights.push_back(prod);
            // 剩下的质因数各自作为一个权重
            for (int i = num_first; i < m; i++) {
                weights.push_back(primes[i]);
            }
        }
        
        // --- Step 3: 贪心匹配并计算总和 ---
        // 将贡献次数也从大到小排序
        sort(contrib.rbegin(), contrib.rend());

        long long ans = 0;
        // 最大的贡献次数 * 最大的权重
        for (int i = 0; i < n - 1; i++) {
            long long w_val = weights[i] % mod; // 权重可能已经很大，需要取模
            long long c_val = contrib[i] % mod; // 贡献次数也可能很大，取模
            ans = (ans + (w_val * c_val) % mod) % mod;
        }

        cout << ans << endl;
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N log N + M log M) 的说。

  • 计算子树大小和贡献次数需要 O(N) 的时间。
  • 对 n-1 个贡献次数排序需要 O(N log N)。
  • 读取 m 个质因数需要 O(M)，排序需要 O(M log M)。
  • 最后的计算是 O(N)。
  • 所以总的时间由排序决定，是 O(N log N + M log M) 呐。

• 空间复杂度: O(N + M) 的说。

  • 邻接表 adj 需要 O(N) 空间。
  • parent, size_arr, order, contrib, weights 这些辅助数组和向量都需要 O(N) 级别的空间。
  • primes 向量需要 O(M) 空间。
  • 合起来就是 O(N + M) 啦！

知识点与总结

这道题真是一次愉快的思维体操，喵~ 它融合了好几个重要的知识点：

1. 贡献法思想: 这是解决这类“求所有xx的总和”问题的神兵利器！当直接枚举目标（如点对）太复杂时，不妨切换视角，计算每个基本元素（如边）对总答案的贡献。
2. 贪心策略与排序不等式: Σ(a_i * b_i) 的最大值问题，通过将两个序列按同序排序后配对求解，是贪心算法的一个经典应用。
3. 树的遍历与子树大小计算: 这是树形问题的基本功！无论是递归还是非递归的DFS，熟练掌握计算子树大小、深度等信息的方法都非常重要。代码里用栈实现的非递归DFS是个很棒的技巧，可以防止在链状的树上发生栈溢出。
4. 组合与数论思想: 如何根据质因数构造权重，体现了一定的构造和分类讨论思想，需要仔细分析题目“最小化1的数量”这一约束。
5. 取模运算: 在处理可能很大的数字乘法和加法时，千万不要忘记在每一步都进行取模，否则就会溢出导致WA，这是竞赛中的血泪教训喵！

希望这篇题解能帮助主人理解这道有趣的题目！继续加油哦！(๑•̀ㅂ•́)و✧