Cod sursa(job #1710085)

Utilizator UPB_CodeJunkiesUPB NAIDEN NICOLICIOIU COTET UPB_CodeJunkies Data 28 mai 2016 14:58:49
Problema Revolta Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 2.5 kb
#include <stdio.h>
#include <algorithm>
#include<vector>
#include<queue>
#define pb push_back
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;

int T,n,nrc,L,R;
int v[maxn],grade[maxn],d[maxn];

vector<int> l[maxn];
int q[maxn],sel[maxn],center[2];

vector<int> dist;

void read()
{
    int x,y;

    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d %d",&x,&y);
        l[x].pb(y); grade[y]++;
        l[y].pb(x); grade[x]++;
    }
}

void get_center()
{
    int k;

    L=1; R=0;
    for(int i=1;i<=n;i++)
     if( grade[i]==1 )
      q[++R]=i;

    int nrn=n;
    for(;nrn>2;)
    {
        int cnt=R-L+1; nrn-=cnt;
        for(int i=1;i<=cnt;i++,L++)
        {
           k=q[L];

           for(unsigned j=0;j<l[k].size();j++)
            if(!sel[l[k][j]])
           {
               grade[l[k][j]]--;

               if( grade[l[k][j]]==1 )
                q[++R]=l[k][j], sel[l[k][j]]=1;
           }
        }
    }

    nrc=R-L+1;

    for(int i=0;i<nrc;i++)
     center[i]=q[L+i];

     printf("%d\n",nrc);
     printf("%d %d\n",center[0],center[1]);

}


void dfs(int k)
{
    v[k]=1; d[k]=0;
    for(unsigned int i=0;i<l[k].size();i++)
     if( !v[l[k][i]])
     {
        dfs(l[k][i]);
        d[k]=max(d[k],1+d[l[k][i]]);
     }

     if( l[k].size()==1 ) dist.pb(d[k]);
}

int solve()
{
    int Min= inf;

    dfs(center[0]);
    sort(dist.begin(),dist.end());

    if( dist.size()==1 )
        return dist[dist.size()-1];

    int X = dist[dist.size()-1]-dist[0];
    dist[dist.size()-1]-=X;

    sort(dist.begin(),dist.end());
    Min=min(Min, dist[dist.size()-1]+dist[dist.size()-2] );

    if( nrc<2 ) return Min;
    for(int i=1;i<=n;i++) v[i]=d[i]=0;

    dist.clear();
    dfs(center[1]);
    sort(dist.begin(),dist.end());

    if( dist.size()==1 )
        return dist[dist.size()-1];

    X = dist[dist.size()-1]-dist[0];
    dist[dist.size()-1]-=X;

    sort(dist.begin(),dist.end());
    Min=min(Min, dist[dist.size()-1]+dist[dist.size()-2] );

    return Min;
}

void clear_data()
{
    L=R=0; nrc=0;
    for(int i=1;i<=n;i++)
    {
        v[i]=d[i]=grade[i]=0;
        sel[i]=0;
        l[i].clear();
    }
}

int main()
{
    freopen("revolta.in","r",stdin);
    freopen("revolta.out","w",stdout);

    scanf("%d",&T);
    for(;T;T--)
    {
        read();
        get_center();
        printf("%d\n",solve());
        clear_data();
    }

    return 0;
}