Cod sursa(job #2623638)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 3 iunie 2020 15:27:12
Problema Cerere Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream cin("cezar.in");
ofstream cout("cezar.out");

bool viz[10005];
int n,dis,nr[10005],level[10005],nr1,inclus[10005],exclus[10005],minn,ans,s,d[10005];
priority_queue<pair<int,int>>q;
vector <int> v[20005];

void dfs(int nod){
    viz[nod]=1;
    inclus[nod] = 1;
    for (auto x : v[nod] ) {
        if(!viz[x]){
            level[x]+=level[nod]+1;
            dfs(x);
            inclus[nod] += inclus[x];
        }
    }
    exclus[nod] = n-inclus[nod];
}

void dfs2(int nod, int last) {
    viz[nod]=1;
    if(minn>last - inclus[nod] + exclus[nod]) {
        minn= last - inclus[nod] + exclus[nod];
        ans = nod;
    }
    for ( auto x : v[nod])
        if(!viz[x])
        dfs2(x,last - inclus[nod] + exclus[nod]);
}

int tata[10005];

void dfs3(int nod){
    viz[nod]=1;
    nr[nod]=1;
    for(auto x: v[nod]){
        if(!viz[x]){
            tata[x]=nod;
            dfs3(x);
            if(nod!=ans){
            d[nod]+=d[x]+nr[x];
            nr[nod]+=nr[x];
            q.push({nr[x],x});
            }
            else{
                q.push({nr[x],x});

            }
        }
    }
}
int k,x,y;
int main(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        viz[i]=0;
    }
    for ( int i = 1; i <= n; ++i)
            dis += level[i];
    minn = dis;
    ans=1;
    viz[1]=1;
    for ( auto x : v[1]){
        if(!viz[x])
            dfs2(x,dis);
    }
    for(int i=1;i<=n;i++){
        viz[i]=0;
    }
   dfs3(ans);
    pair<int,int>x1;
    while(k!=0 && !q.empty()){
        q.pop();
        k--;
    }
    for(int i=1;i<=n;i++){
        viz[i]=0;
    }
    while(!q.empty()){
        x1=q.top();
        q.pop();
        s+=x1.first;
    }
    cout<<s;
}