Cod sursa(job #2210851)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 8 iunie 2018 12:04:36
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>

using namespace std;

ifstream fin("capitala.in");
ofstream fout("capitala.out");

const int N=100000;

int n;
int a[N+5],b[N+5];
int d[N+5];

int st,dr,q[N+5];

int main()
{
    fin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        fin>>x>>y;
        if(a[x]==0)
            a[x]=y;
        else
            b[x]=y;
        if(a[y]==0)
            a[y]=x;
        else
            b[y]=x;
    }
    for(int i=1;i<=n;i++)
        if(b[i]==0)
        {
            d[i]=1;
            q[++dr]=i;
        }
    d[0]=99;
    while(st<=dr)
    {
        int nod=q[st];
        st++;
        if(d[a[nod]]==0)
        {
            d[a[nod]]=d[nod]+1;
            q[++dr]=a[nod];
        }
        if(d[b[nod]]==0)
        {
            d[b[nod]]=d[nod]+1;
            q[++dr]=b[nod];
        }
    }
    int bst=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>bst)
        {
            bst=d[i];
            cnt=0;
        }
        if(d[i]==bst)
            a[++cnt]=i;
    }
    fout<<bst-1<<" "<<cnt<<"\n";
    for(int i=1;i<=cnt;i++)
        fout<<a[i]<<" ";
    fout<<"\n";
    return 0;
}