Moe's CF Life

Appearance

D. Tree Jumps - 题解 ​

比赛与标签 ​

比赛: Educational Codeforces Round 175 (Rated for Div. 2) 标签: dfs and similar, dp, trees 难度: *1600

题目大意喵~ ​

主人你好呀~！这道题是关于在一棵有根树上跳跃的有趣问题哦，喵~

我们有一棵 n 个节点的树，根节点是 1。一开始，我们的小芯片就乖乖地待在根节点 1 上。我们可以进行一种特殊的“跳跃”操作：

  1. 移动规则: 从当前节点 v 跳到另一个节点 u，必须满足 u 的深度比 v 的深度恰好多 1 (d_u = d_v + 1)。也就是说，我们只能往更深的一层跳。
  2. 特殊限制:
    • 如果芯片在根节点 (v=1)，它可以跳到下一层（深度为1）的任何一个节点。
    • 如果芯片在非根节点 (v != 1)，它可以跳到下一层的任何一个节点 u，除非 u 是 v 的邻居（也就是 v 的孩子）。

一个“有效序列”就是一个顶点序列，表示了小芯片从根节点出发，按照序列顺序依次访问，并且只访问这些节点所形成的一条合法路径。

我们的任务就是，计算出所有可能的有效序列的总数是多少，结果要对 998244353 取模哦！

解题思路，来分析一下吧！ ​

这道题要求我们计算所有合法路径的数量，一看到“计数”和“路径”，我们聪明的猫猫脑袋里就应该想到动态规划（DP）啦，喵！

我们的 DP 思路是基于树的层次（深度）来进行的。

DP状态定义 ​

很自然地，我们可以定义 dp[u] 为：以节点 u 结尾的有效序列的数量。 我们的最终答案，就是所有 dp[u] 的总和，因为任何一个以 u 结尾的有效序列都是一个需要被计数的答案。

DP状态转移 ​

要计算 dp[u]，我们需要想一想，小芯片是怎么跳到 u 的呢？它一定是从 u 的上一层，也就是深度为 d[u] - 1 的某个节点 v 跳过来的。

我们来根据题目的限制条件，仔细分析一下状态转移方程：

  1. 基础情况 (Base Case): 最短的有效序列就是 [1]，只访问根节点。所以，dp[1] = 1。这是我们所有计算的起点！

  2. 转移逻辑: 假设节点 u 的深度是 k (d[u] = k)。那么，跳到 u 的前一个节点 v 的深度一定是 k-1。

    • 当 k = 1 时 (即 u 是根节点的直接孩子): 根据规则，从根节点 1 可以跳到任何一个深度为 1 的节点。所以，任何一个到达根节点 1 的序列，都可以再下一步跳到 u。因为只有一种序列 [1] 到达根节点，所以 dp[u] = dp[1] = 1。

    • 当 k > 1 时 (即 u 不是根节点的直接孩子): 前一个节点 v 在深度 k-1，并且 v 不是根节点。根据规则，从 v 跳到 u 是被允许的，除非 u 是 v 的孩子。 换句话说，要想到达 u，我们可以从深度为 k-1 的任何一个节点出发，除了 u 的父节点 p[u]。 所以，dp[u] 的值就等于所有深度为 k-1 的节点的 dp 值之和，再减去 dp[p[u]]。 dp[u] = (sum(dp[v] for all v where d[v] = k-1)) - dp[p[u]]

优化一下喵~ ​

每次计算 dp[u] 都去求和一遍 dp[v] 会很慢。我们可以用一个辅助数组 S 来优化它！ 我们定义 S[k] 为所有深度为 k 的节点的 dp 值之和。 S[k] = sum(dp[v] for all v where d[v] = k)

这样，我们的状态转移方程就变得超级清爽啦：

  • 对于深度为 1 的节点 u: dp[u] = S[0] (因为 S[0] = dp[1])
  • 对于深度大于 1 的节点 u: dp[u] = (S[d[u]-1] - dp[p[u]]) % MOD

算法步骤总结 ​

  1. 预处理: 遍历所有节点，计算出每个节点的深度 d[i]，并把所有节点按深度分组存起来。因为题目保证了 p_i < i，我们可以按 i 从 2 到 n 的顺序一次性算完所有深度，非常方便！
  2. 初始化: dp[1] = 1, S[0] = 1。总答案 total_ans 初始化为 1（因为 [1] 是一个有效序列）。
  3. 按层DP: 从深度 k = 1 开始，逐层计算：
    • 对于每个深度为 k 的节点 u，使用上面的转移方程计算 dp[u]。
    • 将计算出的 dp[u] 累加到 S[k] 中。
    • 当一层（深度 k）的所有节点都计算完毕后，S[k] 就是这一层所有 dp 值的和。我们将 S[k] 加到 total_ans 中。
  4. 最终答案: 循环结束后，total_ans 就是我们要求的总数啦！

这样一步步下来，问题就迎刃而解了，是不是很简单呢，喵~

代码实现喵~ ​

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> p(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        std::cin >> p[i];
    }

    // 步骤1: 计算深度并将节点按深度分组
    // p_i < i 的约束保证了我们在计算 d[i] 时, d[p[i]] 已经算好了, 喵~
    std::vector<int> d(n + 1, 0);
    std::vector<std::vector<int>> nodes_at_depth(n);
    int max_depth = 0;
    nodes_at_depth[0].push_back(1); // 根节点1在深度0

    for (int i = 2; i <= n; ++i) {
        d[i] = d[p[i]] + 1;
        max_depth = std::max(max_depth, d[i]);
        if (d[i] < n) {
            nodes_at_depth[d[i]].push_back(i);
        }
    }

    // 步骤2 & 3: 动态规划
    long long MOD = 998244353;
    // dp[u] = 以节点 u 结尾的有效序列数量
    std::vector<long long> dp(n + 1, 0);
    // S[k] = 所有深度为 k 的节点的 dp 值之和
    std::vector<long long> S(max_depth + 1, 0);

    // Base Case: 序列 [1] 是有效的
    dp[1] = 1;
    S[0] = 1;
    long long total_ans = 1; // 初始答案包含序列 [1]

    // 按深度 k = 1, 2, ... 迭代
    for (int k = 1; k <= max_depth; ++k) {
        // 遍历所有深度为 k 的节点 u
        for (int u : nodes_at_depth[k]) {
            // 要形成一个以 u (深度k) 结尾的序列, 前一个节点 v 必须在深度 k-1
            if (k == 1) {
                // 如果 u 是根的直接孩子, 前一个节点必须是根 (v=1)
                // 从根出发的跳跃总是允许的
                // 所以以 u 结尾的序列数等于以根结尾的序列数
                dp[u] = S[0]; // S[0] 就是 dp[1]
            } else {
                // 如果 u 不是根的直接孩子, 前一个节点 v (深度k-1) 就不是根
                // 跳跃 v -> u 被允许, 当且仅当 u 不是 v 的邻居
                // 因为 d[u] = d[v] + 1, 它们是邻居 <=> v 是 u 的父节点
                // 所以我们可以从深度 k-1 的任何节点 v 跳过来, 除了 v=p[u]
                // 方案数 = (深度k-1的所有dp和) - dp[p[u]]
                dp[u] = (S[k - 1] - dp[p[u]] + MOD) % MOD; // +MOD 防止减出负数
            }
            // 将 dp[u] 累加到 S[k] 中
            S[k] = (S[k] + dp[u]) % MOD;
        }
        // 这一层所有可能的序列都计算完了, 把它们加到总答案里
        total_ans = (total_ans + S[k]) % MOD;
    }

    std::cout << total_ans << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(n) 的说 我们对每个节点只访问了常数次。首先，用一个 for 循环计算所有节点的深度并分组，这是 O(n) 的。然后，在 DP 过程中，我们再次遍历每个节点恰好一次来计算它的 dp 值。所以总的时间复杂度是 O(n) + O(n) = O(n)，非常高效呐！

  • 空间复杂度: O(n) 的说 我们用了几个数组，p, d, dp 都是 O(n) 大小。nodes_at_depth 这个二维向量总共存储了 n 个节点，也是 O(n) 的空间。S 数组的大小是最大深度，最坏情况下也是 O(n)。所以总的空间复杂度是 O(n)。

知识点与总结 ​

这道题真是一道非常经典的树上动态规划问题，主人~！通过解决它，我们可以学到：

  1. 树上DP思想: 很多树上的计数问题都可以通过从根到叶（或反之）的DP来解决。关键在于找到正确的状态定义和状态转移方程。这道题就是按深度（层次）进行DP的一个绝佳范例。
  2. DP优化技巧: 直接计算状态转移可能会很慢，要时刻想着有没有可以优化的方法。本题中用 S[k] 数组来预计算每层的DP和，就是一个把 O(N^2) 级别的计算优化到 O(N) 的经典技巧，类似于前缀和思想。
  3. 巧用输入特性: p_i < i 这个小小的约束，让我们可以用一个简单的循环来建树和计算深度，避免了写复杂的BFS或DFS，让代码变得更简洁。
  4. 模运算细节: 在做减法取模时， (a - b) % MOD 可能会得到负数。安全的写法是 (a - b + MOD) % MOD，这样就能保证结果总是在 [0, MOD-1] 范围内啦。

总之，遇到树上的计数问题，不妨先从DP的角度思考一下，定义好状态，理清转移关系，再看看有没有可以优化的地方，问题也许就迎刃而解了！继续加油哦，主人！喵~ >w<

Released under the MIT License.

Copyright © 2024-present Moe