本文共 1901 字，大约阅读时间需要 6 分钟。

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

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

$------------------我是华丽的分割线(●ˇ\forall ˇ●)-----------------------$

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

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

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

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

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

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

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

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

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

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

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

#include 
   
    #include 
    
     #include 
     
      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-m+1;i--)	ans+=f[i];	cout<
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/105809431 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！