题解：CF1153D Serval and Rooted Tree

DeadDreamX · 2025-01-20 12:02:15 · 题解

题目传送门\ 首先，我们先考虑二分一个 \text{{mid}} ，检查“根结点的最大值会不会 \ge \text{{mid}} ”。那么对于叶子结点 [1,k] 的值，就可以化为 0 和 1 ，表示这个值是不是\ge \text{mid} 。要使根结点的值尽可能大，就要使 1 的使用次数尽可能小，所以设 dp_{i} 表示以 i 为根的子树中叶子结点最少使用多少个 1 ，才能使 i 这个点的值为 1 。先考虑 i 点的操作为取 \min ： i 的儿子一定都要是 1 ，所以 dp_{i}=\sum \limits_{j} dp_{j} （其中 j 为 i 的儿子）。再考虑 i 点的操作为取 \max ： i 的儿子只要有一个为 1 即可，所以 dp_{i}=\min \limits_{j} \{ dp_{j} \} （其中 j 为 i 的儿子）。列出转移方程，我们发现貌似没有用到 \text{mid} ，所以把二分去掉，答案就为 k-dp_{1}+1 。\ code:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m,opt[N],dp[N];
vector<int> e[N];

void dfs(int x)
{
    if(e[x].size()==0)
    {
        dp[x]=1;
        return ;
    }
    int ans1=1e9,ans2=0;
    for(int i=0;i<e[x].size();i++)
    {
        int y=e[x][i];
        dfs(y);
        ans1=min(ans1,dp[y]),ans2+=dp[y];
    }
    if(opt[x]) dp[x]=ans1;
    else dp[x]=ans2;
    return ; 
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",opt+i);
    for(int i=2;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        e[x].push_back(i);
    }
    for(int i=2;i<=n;i++) m+=(e[i].size()==0);
    dfs(1);
    cout<<m-dp[1]+1;
    return 0;
}