Cod sursa(job #99535)

Utilizator mariusdrgdragus marius mariusdrg Data 11 noiembrie 2007 12:34:22
Problema Zvon Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.71 kb
#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

#define pb push_back
#define vi vector<int>
#define vii vector<int> :: iterator

const int maxn = 100100;

int nrt,i,n,din[maxn];
vi vects;
vi vect[maxn];
int ver[maxn];
int s;
int j,x,y;

int max(int i,int j)
{
        return i > j ? i : j;
}

bool cmpf(const int i,const int j)
{
        return i > j;
}


void dfs(int i)
{
        vii it;
        for(it = vect[i].begin(); it != vect[i].end(); ++it)
        {
                if (!ver[*it])
                {
                        ver[*it] = i;
                        dfs(*it);
                }
        }
        for(it =  vect[i].begin(); it != vect[i].end(); ++it)
        {
                if (ver[i] != *it)
                {
                        vects.pb(din[*it]);
                        ++s;
                }
        }
        sort(vects.begin(),vects.end(),cmpf);
        for(j = 0;j < s; ++j)
        {
                din[i] = max(din[i],vects[j] + j + 1);
        }
        vects.clear();
        s = 0;
}


int main()
{
        freopen("zvon.in","r",stdin);
        freopen("zvon.out","w",stdout);
        scanf("%d",&nrt);
        for(;nrt;--nrt)
        {
                scanf("%d",&n);
                for(i = 1;i < n; ++i)
                {
                        scanf("%d %d",&x,&y);
                        vect[x].pb(y);
                        vect[y].pb(x);
                }
                ver[1] = 1;
                dfs(1);
                printf("%d\n",din[1]);
                for(i = 1;i <= n; ++i)
                {
                        ver[i] = 0;
                        vect[i].clear();
                        din[i] = 0;
                }
        }
        return 0;
}