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

· · 题解

第一步是问题转化。

我们知道村庄关系就是一棵树，那么破坏最大化一定是从树根开始雪崩，这样树的大小就是雪崩的破坏程度。而 k 个点其实就是被删去的点，雪崩无法在这里发生也无法来到这里。

那么问题就转化成：给定一棵树，删去 k 个点，使得最大的连通块大小最小。

求最大值最小问题首先想到二分答案。

不难发现 ans 以上的答案是可以实现的，ans 以下的答案无论如何无法实现。所以二分这个界限 ans。

判断有无解很简单，贪心。记块大小的最大值为 m，根据树的性质，我们自底向上遍历，求要删去的最少点数 cnt。

当前子树的大小超过 m 时，我们不得不删去当前节点，并且该节点对于父节点大小的贡献是 0。由于我们自底向上实现，当前节点所有子树的大小一定不会超过 m，所以此时删去该节点是最优的。

如果 cnt < k，说明子树大小可以进一步宽松，否则一定无解。

# include <bits/stdc++.h>
# include <iostream>

using namespace std;

struct Node
{
  int to;
  struct Node* nxt;
};
struct Head
{
    struct Node* nxt;
};

struct Head p[100005];
int siz[100005];
int cnt;

struct Node* ini()
{
    struct Node* tmp = (struct Node*) malloc (sizeof(struct Node));
    tmp->nxt = NULL;
    return tmp;
}

void add_edge(int x,int y)
{
    struct Node* tmp1 = ini();
    tmp1->to = y;
    tmp1->nxt = p[x].nxt;
    p[x].nxt = tmp1;
    return ;
}

int solve(int u,int k)
{
    siz[u] = 1;
    for (struct Node* tmp=p[u].nxt;tmp!=NULL;tmp=tmp->nxt)
    {
        int v = tmp->to;
        solve(v,k);
        siz[u] += siz[v];
    }   
    if (siz[u] > k)
    {
        siz[u]=0;
        cnt++;
    }
    return siz[u];
}

int main (void)
{
    int n,k;
    scanf ("%d %d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        p[i].nxt = NULL;
    }
    for (int i=1;i<n;i++)
    {
        int u,v;
        scanf ("%d",&u);
        v=i+1;
        add_edge(u,v);
    }

    int l=1,r=n;
    int ans;
    while (l <= r)
    {
        cnt=0;
        int mid = (l+r)/2; // mid是最大破坏值 
        solve(1,mid);
        if (cnt > k) // solve得到的是最大破坏值的情况下最少需要几个围墙 
        {
            l = mid+1;
        }
        else
        {
            r = mid-1;
            ans = mid;
        }
    }
    printf ("%d",ans);
    return 0;
}