题目分析

我们有一棵以 $1$ 为根的有根树，边权为 $1$ 分钟。毛毛虫从根出发，需要访问所有节点。它有两种移动方式：

1. 沿着树边爬行，耗时 $1$ 分钟。
2. 从任意节点直接传送回根节点，不耗时，但最多使用 $k$ 次。

访问完所有节点后，毛毛虫可以停在任意节点（不需要返回根）。求完成遍历的最短时间。

如果没有任何传送，要访问所有节点并最终停在某个叶子，最短的走法相当于从根出发走完所有边，并且最后一段到结束叶子的路径不需要返回。总的边数为 $2(n-1)$（每条边一进一出）。如果最终停在某个叶子 $l$，则实际耗时 $= 2(n-1) - depth(l)$，因为从根到 $l$ 的最后一段路径只走了一次。

引入传送后，相当于我们可以多次“省略”从某个位置返回根的过程，每次传送节省的时间与路径有关。

算法思路（贪心 + DFS）

我们可以将问题转化为：从根出发，进行类似于深度优先搜索的遍历，但可以选择在某些叶子处使用传送，从而省去从该叶子回溯到根的路径时间。由于传送后回到根，我们又可以继续遍历其他分支。

一次传送的收益取决于我们在多深的位置选择传送，以及该叶子在 DFS 序中的位置。为了最大化节省时间，我们应当优先选择能够节省最多时间的叶子进行传送。

标程的做法是：

1. 对树进行预处理，计算每个节点的深度 $h[v]$ 和子树的最大深度 $d[v]$。
2. 对每个节点的子节点按照子树最大深度 升序 排序。这样做是为了在 DFS 遍历时，能够将深的子树留到最后访问，从而使得最后一次不返回（或传送）的收益最大化。
3. 遍历所有叶子节点，模拟一种最优的 DFS 访问顺序，计算出在该叶子处使用传送能够节省的时间增益 jump_gain。
4. 将所有叶子的增益排序，取最大的 $k+1$ 个（因为最终停在某个叶子相当于一次“免费”的不返回），从总边数 $2(n-1)$ 中减去这些增益，得到最小耗时。

关键步骤详解

1. 深度与子树高度计算

• $h[v]$：节点 $v$ 的深度（根为 $0$）。
• $d[v]$：以 $v$ 为根的子树中，从 $v$ 到最深叶子的距离（边数）。

void sort_subtrees_by_depth(int v) {
    d[v] = 0;
    h[v] = (v == 1) ? 0 : h[p[v]] + 1;
    for (int u : children[v]) {
        sort_subtrees_by_depth(u);
        d[v] = max(d[v], d[u] + 1);
    }
    sort(children[v].begin(), children[v].end(), comp_by_depth);
}

其中 comp_by_depth 按 $d[u]$ 升序排列。这样排序后，每个节点的子节点列表中，深度最浅的子树排在最前，最深的排在最后。

2. 计算每个叶子的传送增益

对于每个叶子 $v$，我们计算如果在这个叶子使用传送（或不返回），能够节省的分钟数。过程如下：

• 初始化 jump_gain = 0。
• 从叶子 $v$ 向上回溯，直到根：
  • 如果 $v$ 是其父节点 $p[v]$ 的 最后一个孩子（即最深的子树），说明在最优 DFS 顺序中，我们会最后访问这个子树，因此向上回溯的路径可以连续节省。此时将 $v$ 更新为 $p[v]$，并且 jump_gain 加 $1$。
  • 否则，说明这个叶子所在的子树不是父节点的最深子树，回溯路径会在此处中断，无法连续向上节省。此时计算增益为 jump_gain = jump_gain + 1 - h[p[v]]，并终止循环。

为什么这样计算？
想象我们在进行一种特殊的 DFS：每次进入一个子树前，我们先遍历较浅的子树，最后遍历最深的子树。这样当我们从最深子树返回时，可以一路返回到根，沿途的边都只走了一次（节省了返回的代价）。但如果叶子不在最深子树上，那么在父节点处就要转向其他分支，节省的路径高度会大打折扣。

将所有叶子的 jump_gain 收集到数组 leaf_jump_gains 中。

3. 贪心选择最大增益

将 leaf_jump_gains 从大到小排序。
注意：最后一次停留相当于一次“免费的传送”，因此我们实际可以选择 $k+1$ 个最大的增益（将 ++k 处理）。

总耗时初始为 $2(n-1)$（即每条边走两次）。然后从中减去我们选择的 $k$ 个最大增益（注意增益可能为负，此时取 $0$ 不扣减）。

时间复杂度

• DFS 和排序：每个节点的孩子排序总复杂度 $O(n \log n)$（每个节点最多被排序一次，所有子树大小之和为 $n$）。
• 计算叶子增益：每个叶子向上回溯的过程均摊 $O(n)$，因为每个节点在回溯过程中只会被常数次访问。
• 排序增益：$O(L \log L)$，其中 $L$ 为叶子数，$L \le n$。

总体时间复杂度 $O(n \log n)$，满足 $n \le 2 \times 10^5$ 的限制。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 200005;
int d[maxn];      // 子树最大深度（边数）
int h[maxn];      // 节点深度
int p[maxn];      // 父节点
vector<int> leaf_jump_gains;
vector<vector<int>> children;

bool comp_by_depth(int u, int v) {
    return d[u] < d[v];
}

void sort_subtrees_by_depth(int v) {
    d[v] = 0;
    h[v] = (v == 1) ? 0 : h[p[v]] + 1;
    for (int u : children[v]) {
        sort_subtrees_by_depth(u);
        d[v] = max(d[v], d[u] + 1);
    }
    // 按子树深度升序排序
    sort(children[v].begin(), children[v].end(), comp_by_depth);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    children.resize(n + 1);
    for (int i = 2; i <= n; ++i) {
        cin >> p[i];
        children[p[i]].push_back(i);
    }
    sort_subtrees_by_depth(1);
    
    for (int i = 1; i <= n; ++i) {
        if (children[i].empty()) { // 叶子
            int jump_gain = 0;
            int v = i;
            while (v != 1) {
                int sz = children[p[v]].size();
                // 如果 v 是其父节点的最后一个孩子（最深的子树）
                if (children[p[v]][sz - 1] == v) {
                    v = p[v];
                    ++jump_gain;
                } else {
                    jump_gain = jump_gain + 1 - h[p[v]];
                    break;
                }
            }
            leaf_jump_gains.push_back(jump_gain);
        }
    }
    
    sort(leaf_jump_gains.begin(), leaf_jump_gains.end(), greater<int>());
    ++k; // 最后停留不返回相当于多一次传送
    int res = 2 * (n - 1);
    for (int i = 0; i < min(k, (int)leaf_jump_gains.size()); ++i) {
        res -= max(leaf_jump_gains[i], 0);
    }
    cout << res << '\n';
    return 0;
}

总结

本题通过 DFS 预处理子树深度，并对子节点巧妙排序，模拟出最优的 DFS 访问顺序。随后计算每个叶子使用传送可节省的时间，贪心选择最大收益。整个算法在 $O(n \log n)$ 时间内完成，高效且易于实现。