Cod sursa(job #599048)

Utilizator tiganu_dolarMancea Catalin tiganu_dolar Data 27 iunie 2011 21:17:46
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

#define maxim(a,b) (a>b ? a : b)
#define pb push_back
#define NMAX 100005

vector<int> v[NMAX];
char viz[NMAX];
int t,n,m;
int tata[NMAX];
int sol[NMAX];
int vect[NMAX];

void dfs(int nod)
{
    int i,nr,vec,lim=v[nod].size();

    viz[nod]=1;
    
    for(i=0;i<lim;i++)
        if(!viz[vec=v[nod][i]])
            dfs(vec);
        else
            tata[nod]=vec;
    nr=0;
    for(i=0;i<lim;i++)
        if(v[nod][i]!=tata[nod])
            vect[++nr]=sol[v[nod][i]];
    sort(vect+1,vect+nr+1);
    for(i=nr;i>=1;i--)
        sol[nod]=maxim(sol[nod],nr-i+1+vect[i]);
}

int main ()
{
    int i,a,b;
    
    freopen("zvon.in","r",stdin);
    freopen("zvon.out","w",stdout);
    scanf("%d",&t);
    for(;t;t--)
    {
        scanf("%d",&n);
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            v[a].pb(b);
            v[b].pb(a);
        }
        memset(viz,0,sizeof(viz));
        memset(sol,0,sizeof(sol));
        dfs(1);
        printf("%d\n",sol[1]);
        for(i=1;i<=n;i++)
            v[i].clear();
    }
    return 0;
}