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

问题描述

题解

首先，我们可以直接令结点 \(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;

}

巴特西

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

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

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

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

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