Pagini recente » Cod sursa (job #3148161) | Cod sursa (job #663589) | Cod sursa (job #3143552) | Cod sursa (job #2764277) | Cod sursa (job #1511679)
#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;
}