Cod sursa(job #106279)

Utilizator silviugSilviu-Ionut Ganceanu silviug Data 18 noiembrie 2007 15:30:52
Problema Zvon Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.88 kb
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <sstream>
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>

using namespace std;

#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define FOR(i, N, M) for (int i = (int)(N); i <= (int)(M); ++i)
#define FORD(i, N, M) for (int i = (int)(N); i >= (int)(M); --i)
#define FORI(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define TIP(x) (cerr << #x << " = " << (x) << endl)
#define sz size()
#define pb push_back
#define mp make_pair
#define pf first
#define ps second
#define INF 1000000000
#define ALL(x) (x).begin(), (x).end()
#define CLEAR(X) (memset(X, 0, sizeof(X)))
typedef vector<int> VI;
typedef vector<string> VS;
typedef long long LL;

const int MAX_N = 128 * 1024;

int N;
vector<int> vec[MAX_N];
vector<int> wer[MAX_N];
int timp[MAX_N];
bool viz[MAX_N];

void DFS(int nod) {
    viz[nod] = true;
    wer[nod].reserve(vec[nod].sz);

    REP(i, vec[nod].sz) {
        int crt = vec[nod][i];
        if (!viz[crt]) {
            DFS(crt);
            wer[nod].pb(timp[crt]);
        }
    }
    sort(ALL(wer[nod]), greater<int>());
    int mx = 0;
    REP(i, wer[nod].sz) {
        if (mx < wer[nod][i] + (i + 1)) {
            mx = wer[nod][i] + (i + 1);
        }
    }
    timp[nod] = mx;
}

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

    int nrt, a, b;
    scanf("%d", &nrt);
    for (; nrt--;) {
        scanf("%d", &N);

        REP(i, N - 1) {
            scanf("%d %d", &a, &b);
            --a, --b;
            vec[a].pb(b);
            vec[b].pb(a);
        }
        memset(viz, 0, sizeof(bool) * N);
        DFS(0);
        printf("%d\n", timp[0]);

        REP(i, N) wer[i].clear(), vec[i].clear();
    }

	return 0;
}