Linova and Kingdom(树型-贪心)

题目大意：给定一棵树，1为首都（首都可以是工业城市也可以是旅游城市），一共有n个点。

其中要选出k个工业城市，每个工业城市出一个代表去首都，其快乐值是其途径旅游城市(非工业)的个数

求所有快乐值相加的最大值。

emmm这题真的就差一点点啊......

\(\color{Orange}{------------------我是华丽的分割线(●ˇ∀ˇ●)-----------------------}\)

通过观察题目发现选工业城市是有明显的收益的。

比如，选的话最好选叶子节点，叶子节点中选深度较大的又比较好。

如果只选一个城市的话，那肯定选深度最大的叶子。现在选K个，难点在哪里?

在于选了某个节点后，\(\color{Red}{如果再选它的祖先节点，它的收益就会发生变化(减少1)}\).

动态的过程是很难分析的。

不过这里没必要说叶子的收益减少1，不如让它的祖先节点的收益减少1，这样每个节点的收益都是固定的。

这样的话，得到这样一个式子。(dp表示收益，deep表示深度,size表示子树大小)

\[dp[u]=deep[u]-size[u]+1
\]

这样只要先选子节点，再选父节点，收益都被我们算出来了，对dp数组排个序取k个最大的就行。

\(那会不会不选子节点，只选父节点呢?那dp[u]=deep[u]呀!我们的收益就算错了呀!!\)

\(怎么可能......傻也要有个限度呀哈哈!明显子节点的dp值更大，排序后肯定是先选的子节点......\)

#include <iostream>

#include <algorithm>

#include <math.h>

using namespace std;

typedef long long ll;

const int maxn=2e5+9;

ll n,m,deep[maxn],Size[maxn],ans,f[maxn];

struct node{

	int to,nxt;

}d[maxn*2];int head[maxn*2],cnt=1;

void add(int u,int v){

	d[cnt].nxt=head[u],d[cnt].to=v,head[u]=cnt++;

}

void dfs(int now,int fa)

{

	deep[now]=deep[fa]+1;

	Size[now]=1;

	int son=0;

	for(int i=head[now];i;i=d[i].nxt)

	{

		if(d[i].to!=fa)

		{

			son++;

			dfs(d[i].to,now);

			Size[now]+=Size[d[i].to];

		}

	}

	f[now]=deep[now]-Size[now]+1;

}

void ddp(int now,int fa)

{

	for(int i=head[now];i;i=d[i].nxt)

	{

		int v=d[i].to;

		if(v==fa)	continue;

	}

}

int main()

{

	cin>>n>>m;

	for(int i=1;i<n;i++)

	{

		int l,r;

		scanf("%d%d",&l,&r);

		add(l,r);add(r,l);

	}

	deep[1]=-1;

	dfs(1,1);

	sort(f+1,f+1+n);

	for(int i=n;i>=n-m+1;i--)	ans+=f[i];

	cout<<ans;

	return 0;

}

巴特西

Linova and Kingdom(树型-贪心)

最新文章

热门文章