Codeforces Round #551 (Div. 2) D 树形dp

https://codeforces.com/contest/1153/problem/D

题意

一颗有n个点的数,每个点a[i]为0代表取子节点的最小,1代表取最大,然后假设树上存在k个叶子,问你如何将1~k分配给叶子节点使得根节点最大

题解

实际上最后只有一个值能到达根,我们需要计算没用的叶子节点数量
min:相当于将子节点叶子数量相加
max:相当于将子节点叶子数量取最小
ans=叶子数-sz[1]+1

代码

#include<bits/stdc++.h>

#define MAXN 300005

using namespace std;

vector<int>G[MAXN];

int a[MAXN],Sz[MAXN],n,v,lt;

void dfs(int u,int fa){

    int son=0;

    for(auto v:G[u]){

        if(fa==v)continue;

        son++;

        dfs(v,u);

        Sz[u]+=Sz[v];

    }

    if(son==0){lt++;Sz[u]=1;return;}

    if(a[u]==1){

        Sz[u]=n;

        for(auto v:G[u]){

            if(fa==v)continue;

            Sz[u]=min(Sz[v],Sz[u]);

        }

    }

}

int main(){

    cin>>n;

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    for(int u=2;u<=n;u++){

        scanf("%d",&v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(1,0);

    cout<<lt-Sz[1]+1;

}

巴特西

Codeforces Round #551 (Div. 2) D 树形dp

题意

题解

代码

最新文章

热门文章