GreetingsSouvenir - 题解

标签与难度

标签: 二分图匹配, 图论, 树上算法, DFS, 匈牙利算法难度: 2300

题目大意喵~

Nyahello~！各位算法大师们，今天我们遇到了一道关于树和闪亮钻石的有趣问题，喵~

事情是这样子的：我们有一棵有 $n$ 个节点的有根树。每个节点 $u$ 都有一个自己的颜色 $c_u$ 。除此之外，每个节点 $u$ 上还镶嵌着一颗亮晶晶的钻石！我们可以为这颗钻石任意选择一个颜色 $d_u$ 。

当我们在节点 $u$ 上选择了钻石颜色 $d_u$ 后，这颗钻石就会施展魔法，点亮 $u$ 的整个子树里所有颜色恰好为 $d_u$ 的节点。被点亮的节点数量，我们称之为 $k_u$ 。

然后呢，这颗钻石会获得一个“闪耀值”，这个值等于 $k_u \cdot d_u$ 。

我们的任务是，为树上的每一个节点 $u$ 都选择一个钻石颜色 $d_u$ ，从而得到一个包含 $n$ 个闪耀值的集合。我们的目标是，让这个集合的 mex 值最大化！

忘了说，一个非负整数集合的 mex 值，就是指不在这个集合里的最小非负整数。比如说，集合 {0, 1, 3, 4} 的 mex 就是 2，因为 0 和 1 都在，但 2 不在，喵~

简单来说，就是要我们通过巧妙地选择钻石颜色，尽可能地凑出从 0 开始的连续整数序列 0, 1, 2, ... 作为闪耀值。我们能凑到的最长连续序列的长度，就是我们想要的答案啦！

解题思路分析

这道题看起来有点复杂，要把节点、子树、颜色、闪耀值和 mex 联系在一起，但别怕，我们一步步把它拆解开，就像解开一团毛线球一样，喵~

核心问题的转化

我们的目标是最大化闪耀值集合的 mex。要让 mex 值最大为 $M$ ，意味着我们必须能够生成 $0, 1, 2, \dots, M-1$ 这 $M$ 个闪耀值。因为我们总共有 $n$ 个节点，每个节点产生一个闪耀值，所以我们最多只能用 $n$ 个不同的闪耀值。这意味着，我们需要从 $n$ 个节点中选出 $M$ 个不同的节点，分别让它们产生 $0, 1, \dots, M-1$ 这 $M$ 个闪耀值。

这听起来是不是很像一个分配任务的问题？我们有 $M$ 个任务（生成闪耀值 $0, 1, \dots, M-1$ ），和 $n$ 个工人（树上的节点）。如果一个工人能完成某个任务，它们之间就有一条连线。我们要看是否能给每个任务都分配一个不同的工人。

这正是二分图匹配的经典模型呀，喵！

我们可以构建一个二分图：

左部节点：代表我们想要生成的闪耀值，即 $0, 1, 2, \dots$ 。
右部节点：代表树上的 $n$ 个节点，即 $1, 2, \dots, n$ 。
边：如果在右部的节点 $u$ 能够产生左部的闪耀值 $s$ ，我们就在 $s$ 和 $u$ 之间连一条边。

我们的问题就变成了：在这个二分图中，我们能找到的从 $0$ 开始的最长连续的一段闪耀值，它们都能和不同的树节点成功匹配？

寻找最大匹配的策略

如何找到这个最长的连续段呢？有两种常见的策略：

二分答案：二分答案 $M$ ，然后检查是否存在一个大小为 $M$ 的匹配，覆盖所有左部节点 $0, \dots, M-1$ 。这个方法可行，但每次 check 都要重新建图跑一次最大匹配，可能会有点慢。
增量匹配：这是一个更自然、更贪心的想法。我们按顺序来：
- 先尝试生成闪耀值 0。
- 如果成功了，再尝试在保留 0 的基础上，额外生成 1。
- 如果也成功了，再尝试生成 2...
- 以此类推，直到我们第一次无法生成某个值 ans 为止。那么，我们能生成的最大连续序列就是 0, 1, ..., ans-1，所以答案就是 ans。

这个增量匹配的过程，正好可以用匈牙利算法（或基于DFS/BFS的增广路算法）来完美实现。当我们尝试为新的闪耀值 $j$ 寻找一个匹配节点 $u$ 时：

如果 $u$ 还没被匹配，太棒了，直接把 $j$ 和 $u$ 匹配上！
如果 $u$ 已经被一个旧的闪耀值 $k$ 匹配了，我们就尝试给 $k$ “挪个窝”，看看能不能给 $k$ 找到另一个可以匹配的节点。如果 $k$ 能成功挪走，那 $u$ 就空出来了，可以和 $j$ 匹配啦！

这个寻找“挪窝”路径的过程，就是寻找增广路。

如何构建二分图？

现在最关键的一步，就是确定图中的边。即，对于一个节点 $u$ 和一个目标闪耀值 $s$ ，节点 $u$ 究竟能不能产生闪耀值 $s$ 呢？

根据定义， $s = k_u \cdot d_u$ 。其中 $k_u$ 是在节点 $u$ 的子树中，颜色为 $d_u$ 的节点数量。所以，要让节点 $u$ 产生闪耀值 $s$ ，我们必须找到一个钻石颜色 $d$ 使得：

s = d \times (\text{在 } u \text{ 的子树中颜色为 } d \text{ 的节点数})

这意味着，我们需要对于每个节点 $u$ ，枚举所有可能的钻石颜色 $d$ ，计算出对应的 $k_u$ 和闪耀值 $s = k_u \cdot d$ ，然后添加一条边 $(s, u)$ 。

一个特别的观察：任何节点 $u$ 都可以产生闪耀值 $0$ ！只要我们选择一个在 $u$ 的子树中从未出现过的颜色作为钻石颜色 $d_u$ ，那么 $k_u$ 就会是 $0$ ，闪耀值自然也是 $0$ 。所以，对于闪耀值 $0$ ，它可以和任何一个节点匹配。

计算子树颜色数量：为了高效地计算任意节点 $u$ 子树内的颜色数量，我们可以先对整棵树进行一次深度优先搜索（DFS），计算出每个节点的 DFS 序。这样，每个节点的子树就对应到了 DFS 序数组中的一个连续区间 [dfn_in[u], dfn_out[u])。

于是，建图的完整流程如下：

对树进行一次 DFS，得到所有节点的子树在 DFS 序数组中对应的区间。
对于每一个节点 $u \in [1, n]$ ： a. 遍历 $u$ 子树中的所有节点（通过其 DFS 序区间）。 b. 统计子树中每种颜色的出现次数，得到一个频率表 counts。 c. 遍历这个频率表，对于每个 (颜色 d, 次数 k) 对，计算闪耀值 $s = d \cdot k$ 。 d. 如果 $s \le n$ （因为我们最多关心到 $n$ 的闪耀值），就在二分图中记录下：节点 $u$ 可以产生闪耀值 $s$ 。
对于闪耀值 $0$ ，所有节点都可以产生它。

算法总览

结合以上分析，我们的完整算法就清晰啦：

预处理：用一次 DFS 遍历树，记录下每个节点子树对应的 DFS 序区间。
建图：
- 创建一个数据结构 can_produce[s]，用来存储所有能产生闪耀值 $s$ 的节点列表。
- 对于每个节点 $u=1, \dots, n$ $u = 1, \dots, n$ ：
  - 获取 $u$ 子树中所有节点的颜色。
  - 统计这些颜色出现的频率。
  - 根据频率计算所有可能的闪耀值 $s$ 。
  - 如果 $s \le n$ ，则将 $u$ 加入到 can_produce[s] 列表中。
- 别忘了，所有节点都能产生 0，所以 can_produce[0] 包含所有节点 $1, \dots, n$ 。
增量匹配：
- 初始化 ans = 0 和一个 owner 数组（owner[u] 表示节点 u 被哪个闪耀值匹配了）。
- 从 j = 0 到 n 进行循环：
  - 调用增广路算法 find_path(j)，尝试为闪耀值 j 寻找一个匹配。
  - 如果 find_path(j) 成功，说明我们成功产生了 0, ..., j，那么 ans 就可以增加到 j + 1。
  - 如果失败了，说明我们无法产生 j，那么 ans 就是我们能凑出的最大 mex 值。循环结束。
输出 ans。

这个思路虽然在最坏情况下，建图的复杂度可能比较高，但在实际问题中，由于 shininess <= n 的强力约束，能产生的合法边数量远没有理论上那么多，所以它跑得飞快，足够通过了喵！

代码实现

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

cpp

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

// N 是节点数量的最大值
const int MAXN = 20005;

int n;
std::vector<int> tree_adj[MAXN]; // 存储树的邻接表
int colors[MAXN];               // 每个节点的颜色

// --- DFS 序相关 ---
int dfs_order[MAXN]; // 存储整棵树的DFS序
int dfn_in[MAXN];    // dfn_in[u] 是节点u在dfs_order中的起始位置
int dfn_out[MAXN];   // dfn_out[u] 是u子树在dfs_order中的结束位置（不包含）
int timer = 0;

void build_dfs_order(int u) {
    dfn_in[u] = timer;
    dfs_order[timer++] = u;
    for (int v : tree_adj[u]) {
        build_dfs_order(v);
    }
    dfn_out[u] = timer;
}

// --- 二分图匹配相关 ---
std::vector<int> can_produce[MAXN]; // can_produce[s] 存储能产生闪耀值s的节点列表
int owner[MAXN];                    // owner[u] 记录节点u被哪个闪耀值匹配
bool visited_shininess[MAXN];       // 在一次增广路搜索中，标记闪耀值是否被访问过

// 寻找增广路的DFS函数
bool find_path(int s) {
    if (visited_shininess[s]) {
        return false;
    }
    visited_shininess[s] = true;

    for (int u : can_produce[s]) {
        // 如果节点u未被匹配，或者u的当前匹配对象可以找到新的匹配
        if (owner[u] == -1 || find_path(owner[u])) {
            owner[u] = s;
            return true;
        }
    }
    return false;
}

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

    std::cin >> n;

    for (int i = 2; i <= n; ++i) {
        int parent;
        std::cin >> parent;
        tree_adj[parent].push_back(i);
    }

    for (int i = 1; i <= n; ++i) {
        std::cin >> colors[i];
    }

    // 1. 预处理：构建DFS序
    build_dfs_order(1);

    // 2. 建图：计算所有可能的 (shininess, node) 对
    std::vector<int> subtree_colors;
    std::vector<int> color_counts(n + 1);

    // 任何节点都可以产生 shininess 0
    for (int i = 1; i <= n; ++i) {
        can_produce[0].push_back(i);
    }

    for (int u = 1; u <= n; ++u) {
        subtree_colors.clear();
        // 获取u子树中所有节点的颜色
        for (int i = dfn_in[u]; i < dfn_out[u]; ++i) {
            int node_in_subtree = dfs_order[i];
            subtree_colors.push_back(colors[node_in_subtree]);
        }

        // 统计颜色频率
        for (int color : subtree_colors) {
            color_counts[color]++;
        }

        // 计算闪耀值并建边
        for (int color : subtree_colors) {
            if (color_counts[color] > 0) {
                long long shininess = (long long)color * color_counts[color];
                if (shininess <= n) {
                    can_produce[shininess].push_back(u);
                }
                // 清零，避免重复计算
                color_counts[color] = 0;
            }
        }
    }
    
    // 3. 增量匹配
    std::fill(owner + 1, owner + n + 1, -1);
    int max_mex = 0;
    for (int s = 0; s <= n; ++s) {
        std::fill(visited_shininess, visited_shininess + s + 1, false);
        if (find_path(s)) {
            max_mex++;
        } else {
            break;
        }
    }

    std::cout << max_mex << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N^2 + N \cdot |E|)$
- 预处理 (DFS): 遍历整棵树一次，复杂度为 $O(N)$ 。
- 建图: 对于每个节点 $u$ ，我们都遍历了它的整个子树。总的操作次数是所有节点子树大小之和，即 $\sum_{u=1}^{N} |subtree(u)|$ 。这等价于 $\sum_{v=1}^{N} depth(v)$ 。在最坏情况下（比如一条链），这个和是 $O(N^2)$ 。
- 匹配: 我们最多尝试匹配 $N+1$ 个闪耀值。对于每个闪耀值，我们进行一次增广路搜索。单次搜索的复杂度是 $O(V' + E')$ ，其中 $V'$ 是图中的节点数（ $O(N)$ ）， $E'$ 是图中的边数。所以匹配的总复杂度是 $O(N \cdot |E'|)$ 。 $|E'|$ 是我们构建出的边的总数。虽然理论上 $|E'|$ 也能达到 $O(N^2)$ ，但在实际数据和 shininess <= N 的约束下，它通常会小得多。
- 虽然理论最坏复杂度很高，但该算法足以通过此题，说明测试数据并没有卡到最极限的情况，喵~
空间复杂度: $O(N^2)$
- 树的邻接表、颜色、DFS序等辅助数组都需要 $O(N)$ 的空间。
- can_produce 数组是主要空间开销。在最坏情况下，一个节点可能产生 $O(N)$ 个不同的闪耀值，总边数可能达到 $O(N^2)$ ，所以需要 $O(N^2)$ 空间来存储这些边。

知识点总结

这道题是一个很好的例子，展示了如何将一个看似复杂的问题，通过建模转化为我们熟悉的算法模型，喵~

问题建模: 核心是识别出 “最大化mex” 与 “分配任务” 之间的联系，从而想到二分图匹配模型。
增量法: 与其二分答案，不如采用增量匹配的策略，从 $0$ 开始逐个尝试匹配，代码更简洁，思路也更直接。
匈牙利算法 (Augmenting Path): 解决二分图最大匹配的经典算法，通过寻找增广路来不断扩大匹配数。
树上技巧 (DFS序): 使用 DFS 序将子树问题转化为序列上的区间问题，是处理树上子树统计问题的常用高效方法。

希望这篇题解能让你有所收获，如果还有不明白的地方，随时可以再来问我哦！一起加油，变得更强，喵~！

GreetingsSouvenir - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心问题的转化 ​

寻找最大匹配的策略 ​

如何构建二分图？ ​

算法总览 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​