题解 CF1153D 【Serval and Rooted Tree】

· · 题解

题目大意

给定一个有 n 个结点的以 1 为根的树，每个结点上有一个操作类型 0 或 1 。

操作类型 0 代表该节点的权值为其所有儿子的权值的最小值，操作类型 1 代表该节点的权值为其所有儿子的权值的最大值。叶子结点的权值没有意义，可以忽略。

假设这棵树有 k 个叶子，你需要在每个叶子上填入数字 1-k ，使得按如上计算结点权值后，结点 1 的权值最大，输出这个最大值。

2\le n\le 3\times 10^5

解题思路

假设答案为 x ，如果一个结点上的操作为 \min ，则其要求其每个儿子结点的值都大于 x ，如果一个结点上的操作为 \max ，其要求其中一个儿子结点的值大于 x 。

按照上面的操作，如果我们到达了一个叶子结点，那么我们就需要一个大于等于 x 的数来填入这个格子中，由于 x 在遍历全树时不会改变，我们只需要找到一种方式，使得最后到达的叶子结点数最少。

我们发现在这个过程中唯一能控制到达叶子结点数的是操作类型 \max ，在计算该节点信息的过程中，我们只需选择一个叶子结点数最小的子树，即对其所有儿子能选择的最小叶子节点数取 \min 。

在操作 \min 时，由于其要求每个儿子结点的值都大于 x ，我们要对其儿子能选择的最小叶子结点数求和，作为该节点能选择的最小叶子结点数。

最后，我们发现根节点能选择的最小叶子结点数 ans 是和 x 无关的，而这个结点数的意义是至少需要选择 ans 个值大于等于 x 的数，那么我们的 x 最大为 k+1-ans 。

代码展示

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=600010;
int n,op[maxn],x,k;
int cur,h[maxn],nxt[maxn],p[maxn];
int f[maxn];
void add_edge(int x,int y)
{
    cur++;
    nxt[cur]=h[x];
    h[x]=cur;
    p[cur]=y;
}
void dfs(int x,int fa)
{
    int ch=0;
    if(op[x]==1)f[x]=2e9;
    for(int j=h[x];j;j=nxt[j])if(p[j]!=fa)
    {
        ch++;
        dfs(p[j],x);
        if(op[x]==0)f[x]+=f[p[j]];
        else f[x]=min(f[x],f[p[j]]);
    }
    if(!ch)k++,f[x]=1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",op+i);
    for(int i=2;i<=n;i++)scanf("%d",&x),add_edge(i,x),add_edge(x,i);
    dfs(1,-1);
    printf("%d\n",k+1-f[1]);
    return 0;
}