Cod sursa(job #100480)

Utilizator raula_sanChis Raoul raula_san Data 12 noiembrie 2007 12:00:21
Problema Zvon Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.99 kb
#include <cstdio>
#include <vector>
#include <queue>

#define maxN 100001

using namespace std;

int Tt;
int N;
int Nr[maxN];
int Niv[maxN];
int Nmax[maxN];
int T[maxN];

struct elem
{
    int nod;
    int nmax;
    int nr;
};

class comp
{
    public:
        bool operator()(elem a, elem b)
        {
            if(a.nr == b.nr)
                return a.nmax < b.nmax;

            else
                return a.nr < b.nr;
        }
};

vector <int> V[maxN];
queue <int> q;
priority_queue<elem, vector <elem>, comp> pq;

void df(int nod)
{
    ++ Nr[nod];

    int i, n = V[nod].size();

    if(!n) Nmax[nod] = Niv[nod];

    for(i=0; i<n; ++i)
    {
        Niv[V[nod][i]] = Niv[nod] + 1;
        df(V[nod][i]);
        Nr[nod] += Nr[V[nod][i]];

        if(Nmax[V[nod][i]] > Nmax[nod])
            Nmax[nod] = Nmax[V[nod][i]];
    }
}

void bfs()
{
    q.push(1);

    int nod, i, k, n;
    elem x;

    while(q.empty() == false)
    {
        nod = q.front();
        q.pop();

        n = V[nod].size();

        for(i=0; i<n; ++i)
        {
            x.nod = V[nod][i];
            x.nr = Nr[x.nod];
            x.nmax = Nmax[x.nod];
            pq.push(x);
        }

        k = 1;

        while(pq.empty() == false)
        {
            x = pq.top();
            pq.pop();
            q.push(x.nod);

            T[x.nod] = T[nod] + k;
            ++ k;    
        }
    }
}

int main()
{
    freopen("zvon.in", "rt", stdin);
    freopen("zvon.out", "wt", stdout);

    int i, a, b;

    for(scanf("%d", &Tt); Tt; --Tt)
    {
        for(scanf("%d", &N), i=1; i<N; ++i)
        {
            scanf("%d %d", &a, &b);
            V[a].push_back(b);
        }    

        df(1);
        bfs();

        int sol = 0;

        for(i=1; i<=N; ++i)
        {
            sol = T[i] > sol ? T[i] : sol;
            Nr[i] = 0;
            Niv[i] = 0;
            Nmax[i] = 0;
            T[i] = 0;
            V[i].clear();
        }

        printf("%d\n", sol);
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}