Pagini recente » Cod sursa (job #2056718) | Cod sursa (job #1740950) | Cod sursa (job #556475) | Cod sursa (job #1235531) | Cod sursa (job #581126)
Cod sursa(job #581126)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define N 100010
int n;
vector< int > g[N];
int a[N];
inline void refresh() {
for(int i=1; i<=n; ++i)
g[i].clear();
}
inline void citire() {
scanf("%d",&n);
int x,y;
for(int i=1; i<n; ++i) {
scanf("%d%d",&x,&y);
g[x].pb(y);
g[y].pb(x);
}
}
bool compar(const int &x,const int &y) {
return (a[x]>a[y]);
}
void dfs(int nod,int tata) {
for(size_t i=0,lim=g[nod].size(); i<lim; ++i) {
if(g[nod][i]==tata)
continue;
dfs(g[nod][i],nod);
}
sort(g[nod].begin(),g[nod].end(),compar);
int t=0;
a[nod] = 0;
for(int i=0,lim=g[nod].size(); i<lim; ++i) {
if(g[nod][i]==tata)
continue;
++t;
if(a[nod]<a[g[nod][i]]+t)
a[nod] = a[g[nod][i]]+t;
}
}
int main() {
freopen("zvon.in","r",stdin);
freopen("zvon.out","w",stdout);
int T;
scanf("%d",&T);
for(; T>0; --T) {
refresh();
citire();
dfs(1,0);
printf("%d\n",a[1]);
}
return 0;
}