Cod sursa(job #1511679)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 27 octombrie 2015 00:26:27
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define DIM 100010
using namespace std;

int node1, node2, T[DIM];
int nrTests, nrNodes;
int Marked[DIM], nrSons;
int Values[DIM], D[DIM];
vector <int> Edges[DIM];

void resetValues ()
{
    for (int i = 1; i < DIM; i ++)
        Edges[i].resize(0);

    memset (Marked, 0, sizeof (Marked));
    memset (  D   , 0, sizeof (  D   ));

    return;
}

void DFS (int node)
{
    Marked[node] = 1;

    vector <int> :: iterator it;
    for (it = Edges[node].begin(); it != Edges[node].end(); it ++)
    {
        int nextNode = *it;

        if (!Marked[nextNode])
        {
            DFS (nextNode);
            T[nextNode] = node;
        }
    }

    nrSons = 0;
    for (it = Edges[node].begin(); it != Edges[node].end(); it ++)
    {
        int nextNode = *it;

        if (T[nextNode] == node)
            Values[++nrSons] = D[nextNode];
    }

    sort (Values + 1, Values + nrSons + 1);

    for (int i = nrSons; i >= 1; i --)
        D[node] = max (D[node], Values[i] + (nrSons - i + 1));

    return;
}

int main ()
{
    freopen ("zvon.in" ,"r", stdin );
    freopen ("zvon.out","w", stdout);

    scanf ("%d", &nrTests);

    for (int t = 1; t <= nrTests; t ++)
    {
        scanf ("%d", &nrNodes);

        for (int i = 1; i < nrNodes; i ++)
        {
            scanf ("%d %d", &node1, &node2);

            Edges[node1].push_back(node2);
            Edges[node2].push_back(node1);
        }

        DFS (1);
        printf ("%d\n", D[1]);

        resetValues ();
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}