Cod sursa(job #1584962)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 30 ianuarie 2016 17:09:14
Problema Zvon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

const int Mn = 1e5 + 6;

int n,pos = 0;
char buff[Mn];
vector< int > g[Mn],v;

void read(int &num)
{
    num = 0;
    char sign = '+';

    while (!isdigit(buff[pos]))
    {
        sign = buff[pos];

        if (++pos == Mn)
           fread(buff,1,Mn,stdin),pos = 0;
    }

    while (isdigit(buff[pos]))
    {
        num = num * 10 + buff[pos] - '0';

        if (++pos == Mn)
           fread(buff,1,Mn,stdin),pos = 0;
    }

    if (sign == '-')
       num *= -1;
}

bool comp(int a,int b)
{
    return (a >= b);
}

int dfs(int node,int parent)
{
    v.clear();
    int val = 0;

    for (int it = 0;it < g[node].size();it++)
        if (g[node][it] != parent)
           v.push_back(dfs(g[node][it],node));

    if (v.size() == 0)
       return 0;

    sort(v.begin(),v.end(),comp);

    for (int it = 0;it < v.size();it++)
        val = max(it + 1 + v[it],val);

    return val;
}

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

     int t;
     read(t);

     for (;t;t--)
     {
         read(n);

         for (int i = 1;i <= n;i++)
             g[i].clear();

         for (int i = 1;i < n;i++)
         {
             int x,y;
             read(x);
             read(y);
             g[x].push_back(y);
             g[y].push_back(x);
         }

         printf("%d\n",dfs(1,0));
     }

  return 0;
}