BZOJ4027/LG4107 「HEOI2015」兔子与樱花 树形DP+贪心

问题描述

LG4107

题解

首先，我们可以直接令结点 \(x\) 的权值为 \(c[x]+son_x\) ，发现将 \(x,y\) 合并，相当于增加 \(c[x]+c[y]-1\) 的重量。

容易想到对于每个结点 \(x\) ，贪心的从小到大合并 \(c[y],y \in son(x)\) ，可以获得最大的答案。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){fh=-1;ch=getchar(); }
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=2000007;

int n,m,ans;
int c[maxn];

vector<int>son[maxn];

bool comp(int x,int y){
    return c[x]<c[y];
}

void dp(int x){
    if(son[x].size()==0) return;
    for(auto y:son[x]) dp(y);
    sort(son[x].begin(),son[x].end(),comp);
    c[x]+=son[x].size();
    for(auto y:son[x]){
        if(c[x]+c[y]-1<=m){
            c[x]+=c[y]-1;
            ++ans;
        }
        else break;
    }
}

int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++) read(c[i]);
    for(int i=1,k;i<=n;i++){
        read(k);
        for(int j=1,x;j<=k;j++){
            read(x);++x;
            son[i].push_back(x);
        }
    }
    dp(1);
    printf("%d\n",ans);
    return 0;
}