Cod sursa(job #1495280)

Utilizator GinguIonutGinguIonut GinguIonut Data 2 octombrie 2015 20:45:56
Problema Zvon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <string.h>
#include <vector>
#include <algorithm>
#define nMax 100009
using namespace std;
ifstream fin("zvon.in");
ofstream fout("zvon.out");
vector<int> G[nMax];
vector<int> timp[nMax];
int t, test, n, i, a, b, dist[nMax];
int cmp(int i, int j)
{
    return dist[i]>dist[j];
}
void DFS(int node, int tata)
{
    int x=0;
    for(vector<int>::iterator it=G[node].begin();it!=G[node].end();it++)
        if(*it!=tata)
            DFS(*it, node);
    sort(timp[node].begin(), timp[node].end(), cmp);
    for(vector<int>::iterator tit=timp[node].begin();tit!=timp[node].end();tit++)
    {
        ++x;
        dist[node]=max(dist[node], dist[*tit]+x);
    }
    timp[tata].push_back(node);
}
int main()
{
    fin>>test;
    for(t=1;t<=test;t++)
    {
        fin>>n;
        for(i=1;i<n;i++)
        {
            fin>>a>>b;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        DFS(1, 0);
        fout<<dist[timp[0][0]]<<'\n';
        for(i=1;i<=n;i++)
        {
            G[i].erase(G[i].begin(), G[i].end());
            timp[i].erase(timp[i].begin(), timp[i].end());
        }
    }
    return 0;
}