「CF1918F」Caterpillar on a Tree

· · 题解

思路

口胡一个早读胡出来的……感觉 pyt 讲得不是很透。

为了使得操作同质化，不难首先想到：将 k+1\rightarrow k，这样最后一定要回到根节点。

想象一下我们在树上行走的过程，肯定是一个叶子走完了就去下一个（这样也能保证每个点都经过）。这样一定每条边经过 2 次（一来一回）。所以如果没有传送门，答案就是 2(n-1)。

考虑传送门带来的影响。首先是使用它的位置：一定是到了叶子节点用。

又，什么时候使用？发现对于一棵子树 x，我们肯定是把传送门在最深的节点使用。因为使得总步数尽量少，所以我们肯定希望这个最深的点是子树中走到的最后一个，使得我们不用再向上返回，造成太多步数的浪费。

推导一下（这里假设 dep_1=0）：显然，访问完这个子树后我们需要至少回到根节点。设这个点为 b_x，那么直接返回的代价是 dep_{b_x}-dep_{fa_x}=dep_{b_x}-dep_x+1。

如果使用传送门，那么我们下一步肯定也是要走到父亲的（但是从根节点走），所以代价是 dep_{fa}=dep_x-1。

两者相减就得到：dep_{b_x}-2\times dep_x+2，也就是在 x 节点中的 b_x 处使用传送门可以使节省的代价。排序过后取前 k 个就行了。

而因为我们是对每个节点都计算了 b_x，所以一定能保证每个叶子都被取到，并且每个叶子被取到的位置都是最优的。（注意：我们之前所说返回到父亲节点是不严谨的，但是这样做可以保证每个叶子节点最终要回到的位置是最上面的，也就是最优的）

实现细节

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N = 5e5 + 5; int read();
int n, k, maxn[N], dep[N], b[N], ans;
bool vis[N]; vector <int> G[N];
struct node {
    int id, x;
    friend bool operator < (node a, node b) { return a.x > b.x; }
} a[N];
void dfs(int x, int fa) {
    maxn[x] = dep[x] = dep[fa] + 1; b[x] = x;
    for(int i = 0;i < G[x].size(); ++i) {
        int to = G[x][i];
        dfs(to, x);
        if(maxn[to] > maxn[x]) maxn[x] = maxn[to], b[x] = b[to];
    }
}
signed main() {
    cin >> n >> k; ++k; ans = 2 * (n - 1);
    for(int i = 2;i <= n; ++i) G[read()].pb(i);
    dep[0] = -1; dfs(1, 0); // dep[1] = 0 
    for(int i = 2;i <= n; ++i) a[i].id = b[i], a[i].x = maxn[i] - 2 * dep[i] + 2;
    sort(a + 1, a + n + 1); 
    for(int i = 1, cnt = 1;i <= n and cnt <= k; ++i) {
        if(a[i].x <= 0) break ;
        if(vis[a[i].id]) continue ;
        ans -= a[i].x, vis[a[i].id] = 1; ++cnt;
    }
    cout << ans; 
    return 0; 
}
int read() {
    char c; int sum = 0; while(c < '0' or c > '9') c = getchar();
    while(c >= '0' and c <= '9') sum = (sum << 3) + (sum << 1) + (c ^ 48), c = getchar();
    return sum; 
}