Cod sursa(job #915759)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 15 martie 2013 12:10:35
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("zvon.in");
ofstream fout("zvon.out");

vector<int> v[100001];
bool used[100001];
int T, n, t[100001];
int sol[100001];

int get_root()
{
    int x  = 1;
    while(t[x]!=0)
        x = t[x];
    return x;
}

void clear_all()
{
    for(int i=1;i<=n;i++)
    {
        used[i] = false;
        sol[i] = t[i] = 0;
        v[i].resize(0);
    }
}

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

int dfs(int nod)
{
    vector<int > vec;
    used[nod] = true;
    for(unsigned int i=0;i<v[nod].size();i++)
        if(!used[v[nod][i]])
        {
            int d = dfs(v[nod][i]);
            vec.push_back(sol[v[nod][i]]);
        }
    sort(vec.begin(),vec.end(),comp);
    for(unsigned int i=0;i<vec.size();i++)
        vec[i] += i;
    sort(vec.begin(),vec.end(),comp);
    if(!vec.empty())
        sol[nod] = vec[0] + 1;
}

int main()
{
    fin>>T;
    for(int q=1;q<=T;q++)
    {
        fin>>n;
        int a,b;
        for(int i=1;i<n;i++)
        {
            fin>>a>>b;
            t[b] = a;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        int root = get_root();
        dfs(root);
        fout<<sol[root]<<'\n';
        clear_all();
    }


    fin.close();
    fout.close();
    return 0;
}