daily 1

CF 1336Ad

简单贪心，对于每个工业国，如果选到了它那么他的子树肯定都被选择了，那么贡献就是dep[i]-(siz[i]-1);
之后sort一下再计算就好了

void solve(){
  int n,k;cin>>n>>k;
  vector<vector<int>>E(n+1);
  for(int i=0;i<n-1;++i){
    int a,b;cin>>a>>b;
    E[a].push_back(b);
    E[b].push_back(a);
  }
  vector<ll>dep(n+1),siz(n+1);
  function<void(int,int)>dfs=[&](int x,int f){
    siz[x]=1;
    for(int v:E[x]){
        if(v==f)continue;
        dep[v]=dep[x]+1;
        dfs(v,x);
        siz[x]+=siz[v];
    }
    dep[x]-=(siz[x]-1);
  };
  dfs(1,0);
  sort(dep.begin()+1,dep.end(),greater<ll>());
  ll ans=accumulate(dep.begin()+1,dep.begin()+k+1,0ll);
  cout<<ans<<'\n';
  return;
}

这两天都少做点，准备面试了，要背的东西太多了