|
题目大意：给定一棵树，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;
}