题解：P13918 [PO Final 2024] 雪崩 / Avalanche

_std_xzh · 2025-10-27 18:01:02 · 题解

这道题其实并不复杂。

SOLUTION

首先，这道题本蒟蒻原本想的是贪心，但 WA 掉了，后来看了其他巨佬的题解，发现贪心是不可做的，贪心的策略，大部分人想的都是把子树大小统计，并将他排序，删掉前 k 个，但这样会影响祖先。

于是我重新审题，发现了关键字眼：在约书亚最优地建造围墙的情况下，亚历山大能造成的最大破坏。很明显的二分答案了，那么所有的东西也就呼之欲出，check 函数也就是用一个 dfs，我们使用一个 cnt 变量统计围墙数量，只要这个 cnt 达不到 k ，那么就是符合要求的。

对于某一棵子树的处理，如果子树大小比 mid 大，那么 cnt 加一，然后因为建了围墙，他的子树以及他自己是不会被其它地方的雪崩影响的，所以子树大小归零。

现在各位可以自己实现一下，还没懂的可以看代码。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n , k , a[N] , sz[N] , cnt;
vector<int>g[N];
void dfs(int x , int now){
    sz[x] = 1;
    for(auto i : g[x]){
        dfs(i , now);
        sz[x] += sz[i];
    }
    if(sz[x] > now){
        cnt++;
        sz[x] = 0;
    }
}
bool check(int mid){
    cnt = 0;
    dfs(1 , mid);
    return (cnt <= k);
}
signed main(){
    cin >> n >> k;
    for(int i = 2;i <= n;i++){
        cin >> a[i];
        g[a[i]].push_back(i);
    }
    int l = 0 , r = n;
    while(l != r){
        int mid = l + r >> 1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}