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

· · 题解

因为要最大值最小，所以一眼二分答案。

假设我们现在的二分中点是 mid。对整棵树进行类似树形 DP 的方法。我们设以点 i 为根的子树大小为 siz_i。显然，如果 siz_i>mid 了，我们就必须建造一堵墙，计数器加一。如果计数器大于 k，就说明不合法，往右边查找，否则就往左边查找。时间复杂度 O((n+m) \log n)。

AC 代码：

#include <iostream>
#include <vector>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5+5;
vector<int> g[N];
int n,k;
int siz[N];
int dfs(int now,int fa,int mid){
    siz[now] = 1;
    int sum = siz[now];//存子树大小
    int sum_ans = 0;//存储子树的答案之和
    for(auto it:g[now]){
        if(it==fa) continue;
        sum_ans+=dfs(it,now,mid);
        sum+=siz[it];
        siz[now]+=siz[it];
    }
    if(sum>mid){//如果超过了 mid，显然要建一堵墙
        siz[now] = 0;
        // cout<<now<<endl;
        return sum_ans+1;//返回答案+1
    }
    return sum_ans;//否则返回答案
}
bool check(int mid){
    int now = dfs(1,-114514,mid);
    // cout<<now<<' ';
    return now<=k;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i = 2;i<=n;i++){
        int x;
        cin>>x;
        g[x].push_back(i);
        g[i].push_back(x);
    }
    int l = 0,r = n;
    int ans = 0;
    while(l<=r){
        int mid = (l+r)>>1;
        // cout<<"Checking "<<mid<<": ";
        if(check(mid)){
            ans = mid;
            r = mid-1;
            // cout<<"Success"<<endl;
        }else l = mid+1/*,cout<<"Unsuccess"<<endl*/;
    }
    cout<<ans;
    return 0;
}