Cod sursa(job #1369139)

Utilizator margikiMargeloiu Andrei margiki Data 2 martie 2015 22:10:32
Problema Zvon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
# include <fstream>
# include <algorithm>
# include <vector>
# define NR 100005
using namespace std;
ifstream f("zvon.in");
ofstream g("zvon.out");
vector <int> v[NR];
int i,j,n,m,o,t,x,y;
int ap[NR], timp[NR];
bool cmp (int a, int b)
{
    if (timp[a]<=timp[b]) return 0;
                     else return 1;
}
void DFS (int k, int tata)
{
    for (int i=0; i<v[k].size(); ++i)
        if (v[k][i]!=tata)
            DFS (v[k][i], k);

    sort (v[k].begin(), v[k].end(), cmp);
    for (int i=0; i<v[k].size(); ++i)
        timp[k]=max(timp[k], timp[v[k][i]]+i+1);
}
int main ()
{
    f>>t;
    for (o=1; o<=t; ++o)
    {
        f>>n; v[n].clear(); timp[n]=0;
        if (n==2)
        {
            g<<"0\n";
            continue;
        }
        for (i=1; i<n; ++i)
        {
            timp[i]=0; v[i].clear ();

            f>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        DFS (1, 0);
        g<<timp[1]<<"\n";
    }

    return 0;
}