C. Linova and Kingdom.Codeforces Round #635 (Div. 2)

链接

https://codeforces.ml/contest/1337/problem/C

题意，从树种选择k个点使得从这k个点到根的路径上经过的未选择的点的数量之和最大

做法

1.读图 这里就不用多说了

2.bfs算出来每个点的深度，即到根的距离

3.再次遍历，在遍历每个点的同时更新每个点的深度。由于选择了某个点时，他的子节点一定在之前被选中了。故可以把他的实际深度看成是  当前深度 -子节点到他的深度。可以用一个zhi数组表示。对于没个点 zhi[i]=zhi[zi1]+zhi[zi2].......+1;

最后根据深度排序，优先选择有效深度最大的点即可

代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
vector <int > g[201000];
queue<int >q;
int vis1[200005];
int vis[200005];

struct trr{
    int num,shen;
}de[200005];
int dst[200005];
int zhi[200005];
bool cmp(const trr &x,const trr &y){
    return x.shen>y.shen;
}

void dfs(int s){
   q.push(s);
   vis[1]=1;
   while(!q.empty()){
           int u=q.front();
           q.pop();
           for(auto i:g[u]){
               if(!vis[i]){
                   de[i].shen=de[u].shen+1;
                   q.push(i);
                   vis[i]=1;
               }
        }
        
   }
}
void bian(){
    for(int j=1;j<=n;j++){
           int u=de[j].num;
           vis1[u]=1;
           for(auto i:g[u]){
               if(!vis1[i]){
                   zhi[i]+=zhi[u]+1;
               }
        }
    }
}
void shu(){
    cin>>n>>k;
    de[1].shen=0;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}
int main(){
    shu();
    dfs(1);
    for(int i=1;i<=n;i++){
        dst[i]=de[i].shen;
        de[i].num=i;
    }
    sort(de+1,de+n+1,cmp);
    bian();
    for(int i=1;i<=n;i++){
        dst[i]-=zhi[i];
    }
    sort(dst+1,dst+n+1,greater<int >());
    long long ans=0;
    for(int i=1;i<=k;i++){
        ans+=dst[i];
    }
    cout<<ans;
}