Pagini recente » Cod sursa (job #2961121) | Cod sursa (job #1775858) | Cod sursa (job #518259) | Cod sursa (job #271816) | Cod sursa (job #1435412)
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
#define NMAX 100001
vector <int> v[NMAX];
int viz[NMAX],d[NMAX];
void dfs(int nod)
{
int nr,maxim,i;
viz[nod]=1;
nr=0;
for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
if(viz[*it]==0)
nr++;
int *x = new int[nr+1];
nr=0;
for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
if(viz[*it]==0) {
dfs(*it);
x[++nr]=d[*it];
}
maxim=0;
sort(x+1,x+nr+1,std::greater<int>());
for(i=1;i<=nr;i++)
maxim=max(maxim,i+x[i]);
free(x);
d[nod]=maxim;
}
int main ()
{
int n,t,i,x,y;
ifstream f("zvon.in");
ofstream g("zvon.out");
f>>t;
while(t--) {
f>>n;
for(i=1;i<=n-1;i++) {
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
memset(viz,0,sizeof(viz));
memset(d,0,sizeof(d));
dfs(1);
g<<d[1]<<'\n';
for(i=1;i<=n;i++)
v[i].clear();
}
f.close();
g.close();
return 0;
}