Cod sursa(job #2418268)

Utilizator TheNextGenerationAyy LMAO TheNextGeneration Data 4 mai 2019 15:20:04
Problema Salvare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
ifstream in("congr.in");
ofstream out("congr.out");
priority_queue<pii, vector<pii>, greater<pii> > h;
const int N = 1e4+5;
vector<int> v[N];
int cost[N],gr[N],dist[N];
bool viz[N];
int main()
{
    int n,k;
    in >> n >> k;
    for (int i = 1; i<n; i++)
    {
        int x,y;
        in >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        gr[x]++;
        gr[y]++;
    }
    for (int i = 1; i<=n; i++)
    {
        if (gr[i] == 1)
            h.push({1,i});
        cost[i] = 1;
    }
    int elim = 0;
    while (!h.empty())
    {
        int now = h.top().second;
        h.pop();
        if (!viz[now])
        {
            elim++;
            viz[now] = 1;
            if (elim == n-k)
                break;
            for (auto it: v[now])
                if (!viz[it])
                {
                    cost[it]+=cost[now];
                    gr[it]--;
                    if (gr[it] == 1)
                        h.push({cost[it],it});
                }
        }
    }
    queue<int> q;
    for (int i = 1; i<=n; i++)
        if (!viz[i])
        {
            dist[i] = 1;
            q.push(i);
        }
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (auto it: v[now])
            if (!dist[it])
            {
                dist[it] = 1+dist[now];
                q.push(it);
            }
    }
    int Max = 0;
    for (int i = 1; i<=n; i++)
        if (dist[i]-1>Max)
            Max = dist[i]-1;
    out << Max << "\n";
    for (int i = 1; i<=n; i++)
        if (!viz[i])
            out << i << " ";
}