Pagini recente » Cod sursa (job #282319) | Cod sursa (job #2817752) | Cod sursa (job #2230129) | Cod sursa (job #3163387) | Cod sursa (job #1887306)
#include <stdio.h>
#include <vector>
#define N 100005
using namespace std;
vector<int> graf[N];
int teste,n,i,a,b,sol;
int t[N]; //t[i]=timpul necesar subarboreluj care incepe cu i pentru a trimite informatia
bool viz[N];
void dfs(int x,int tata)
{
int i,tmax,nr_tmax;
viz[x]=true;
tmax=-1;nr_tmax=0;
for(i=0;i<graf[x].size();i++)
{
if(!viz[graf[x][i]])
dfs(graf[x][i],x);
if(graf[x][i]!=tata)
{
if(t[graf[x][i]]==tmax)
nr_tmax++;
if(t[graf[x][i]]>tmax)
{
nr_tmax=1;
tmax=t[graf[x][i]];
}
}
}
//printf("%d %d\n",tmax,nr_tmax);
t[x]=tmax+nr_tmax;
if(tmax==-1)
t[x]=0;
}
void sterge()
{
for(int i=1;i<=n;i++)
{
viz[i]=false;
graf[i].clear();
t[i]=0;
}
}
int main()
{
FILE *f1,*f2;
f1=fopen("zvon.in","r");
f2=fopen("zvon.out","w");
fscanf(f1,"%d",&teste);
while(teste--)
{
///citire
fscanf(f1,"%d",&n);
for(i=1;i<n;i++)
{
fscanf(f1,"%d%d",&a,&b);
graf[a].push_back(b);
graf[b].push_back(a);
}
///rezolvare
sol=0;
for(i=1;i<=n;i++)
{
if(!viz[i])
dfs(i,0);
if(t[i]>sol)
sol=t[i];
}
fprintf(f2,"%d\n",sol);
sterge();
}
return 0;
}