Pagini recente » Cod sursa (job #1215097) | Cod sursa (job #236109) | Cod sursa (job #3144930) | Cod sursa (job #2429560) | Cod sursa (job #1495280)
#include <fstream>
#include <string.h>
#include <vector>
#include <algorithm>
#define nMax 100009
using namespace std;
ifstream fin("zvon.in");
ofstream fout("zvon.out");
vector<int> G[nMax];
vector<int> timp[nMax];
int t, test, n, i, a, b, dist[nMax];
int cmp(int i, int j)
{
return dist[i]>dist[j];
}
void DFS(int node, int tata)
{
int x=0;
for(vector<int>::iterator it=G[node].begin();it!=G[node].end();it++)
if(*it!=tata)
DFS(*it, node);
sort(timp[node].begin(), timp[node].end(), cmp);
for(vector<int>::iterator tit=timp[node].begin();tit!=timp[node].end();tit++)
{
++x;
dist[node]=max(dist[node], dist[*tit]+x);
}
timp[tata].push_back(node);
}
int main()
{
fin>>test;
for(t=1;t<=test;t++)
{
fin>>n;
for(i=1;i<n;i++)
{
fin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
DFS(1, 0);
fout<<dist[timp[0][0]]<<'\n';
for(i=1;i<=n;i++)
{
G[i].erase(G[i].begin(), G[i].end());
timp[i].erase(timp[i].begin(), timp[i].end());
}
}
return 0;
}