## ➤ Problem Link : 1336A. Linova and Kingdom

## ✅ C++ Solution :

#include<bits/stdc++.h> using namespace std; #define ll long long int #define pb push_back #define pp pair<ll,ll> #define mp make_pair vector<ll> adj[200001]; vector<pp> dpt; ll sz[200001]; ll mx; bool comp(pp x, pp y) { return x.second-sz[x.first] > y.second-sz[y.first]; } ll dfs(int v, ll d, int p) { sz[v]=1; mx=max(d,mx); dpt.pb(mp(v,d)); for(int i=0;i<adj[v].size();i++) if(adj[v][i]!=p) sz[v]+=dfs(adj[v][i],d+1,v); return sz[v]; } int main() { int n,k; mx=0; cin>>n>>k; int x,y; for(int i=1;i<n;i++) { cin>>x>>y; adj[x].pb(y); adj[y].pb(x); } for(int i=1;i<=n;i++) sz[i]=0; dfs(1,0,-1); ll ans=0; sort(dpt.begin(),dpt.end(),comp); for(int i=0;i<dpt.size() && k--;i++) { ans=ans+dpt[i].second-sz[dpt[i].first]+1; // cout<<dpt[i].first<<"\n"; } cout<<ans; }

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

**ðŸ˜‡Happy Learning!!**