1336A - Linova and Kingdom - CodeForces Solution

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


 
#define endl                       "\n"
#define ll                         long long int
#define mod                        998244353
//#define mod                        1000000007
#define pii                        pair<ll,ll>
#define vi                         vector<ll>
#define vvi                        vector<vector<ll>>
#define vpii                       vector<pair<ll,ll>>
#define vvpii                      vector<vector<pair<ll,ll>>>
#define si                         set<ll>
#define mii                        map<ll,ll>
#define umii                       unordered_map<ll,ll>
#define pb                         push_back
#define pob                        pop_back
#define str                        string
#define yes                        (cout<<"YES"<<endl)
#define no                         (cout<<"NO"<<endl)
#define all(type)                  type.begin(), type.end()
#define inf                        1000000000000000005

typedef tree<int, null_type, less<int>,
rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key
//with duplicate ele change<int> to pair-->index will be unique!

/*---------------------------------------------------------------Debug-------------------------------------------------------------------------*/
void debugvi(vector<ll>&v){for(auto x:v)cout<<x<<" ";cout<<endl;}
void debugvvi(vector<vector<ll>>&v){int n=v.size();for(int i=0; i<n; i++, cout<<endl){for(int j=0; j<v[i].size(); j++)cout<<v[i][j]<<" ";}}
/*--------------------------------------------------------------endDebug-----------------------------------------------------------------------*/

/*--------------------------------------------------------------BlackBox-----------------------------------------------------------------------*/
ll expo(ll a, ll b, ll modd){ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % modd; a = (a * a) % modd; b = b >> 1;} return res;}
vector<ll> fact, finv,inv;
void factorial( ll N ) {fact.resize(N) , finv.resize(N) , inv.resize(N); fact[0] = fact[1] = inv[1] = finv[0] = finv[1] = 1;
    for(ll i=2; i<N; i++){ fact[i] = fact[i-1]*i % mod ;  inv[i] = mod-mod/i*inv[mod%i]%mod; finv[i] = finv[i-1]*inv[i]%mod; }}
ll ncr(ll n, ll r){ if(n<r || n<0 || r<0) return 0; return ( fact[n]*finv[r] % mod * finv[n-r] )% mod;}
ll npr(ll n, ll r){ if(n<r || n<0 || r<0) return 0; return ( fact[n]* finv[n-r] )% mod;}
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
//primefactorization in logn with sieve(nlognlogn) precomp maxn->1e7
vector<int> spf(int maxn){vector<int> smallestprime(maxn+1); for(int i=1; i<=maxn; i++)smallestprime[i]=i;for(int i=2; i*i<=maxn; i++){ if(smallestprime[i]==i){for(int j=i*i; j<=maxn; j+=i)
{ if(smallestprime[j]==j) smallestprime[j]=i;}}}return smallestprime;}
vector<int> getpf(ll num, vector<int> &smallestprime){vector<int> p;while(num!=1){p.pb(smallestprime[num]);num/=smallestprime[num];}return p;}
/*-------------------------------------------------------------endBlackBox----------------------------------------------------------------------*/

vector<int> subtree, vt;

int subsize(vector<int> adj[], int index, int pat)
{
    int count=0;
    
    for(auto x: adj[index])
    {
        if(x!=pat)
        count+= subsize(adj, x, index);
    }
    subtree[index]=count;
    return count+1;
}

void dfs(vector<int> adj[], int index, int pat, int deapth)
{
    vt.pb(deapth-subtree[index]);
    
    for(auto x:adj[index])
    {
        if(x!=pat)
        dfs(adj,x, index, deapth+1);
    }
}

int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; t=1;
//cin>>t;

while(t--){
    int n,k,u,v;
    cin>>n>>k;
    
    vector<int> adj[n+1];
    
    for(int i=1; i<n; i++)
    {
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    subtree.resize(n+1);

    subsize(adj, 1, -1);
    
    dfs(adj, 1, -1, 0 );
    
    sort(vt.rbegin(), vt.rend());
    
    ll fox=0;
    
    for(int i=0; i<k; i++)
    fox+=vt[i];
    
    cout<<fox<<endl;
    vt.clear();
    subtree.clear();
}
return 0;
}