Pagini recente » Cod sursa (job #1365492) | Cod sursa (job #965022) | Cod sursa (job #2658695) | Cod sursa (job #850370) | Cod sursa (job #915759)
Cod sursa(job #915759)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("zvon.in");
ofstream fout("zvon.out");
vector<int> v[100001];
bool used[100001];
int T, n, t[100001];
int sol[100001];
int get_root()
{
int x = 1;
while(t[x]!=0)
x = t[x];
return x;
}
void clear_all()
{
for(int i=1;i<=n;i++)
{
used[i] = false;
sol[i] = t[i] = 0;
v[i].resize(0);
}
}
inline bool comp(int a, int b){ return a>b; }
int dfs(int nod)
{
vector<int > vec;
used[nod] = true;
for(unsigned int i=0;i<v[nod].size();i++)
if(!used[v[nod][i]])
{
int d = dfs(v[nod][i]);
vec.push_back(sol[v[nod][i]]);
}
sort(vec.begin(),vec.end(),comp);
for(unsigned int i=0;i<vec.size();i++)
vec[i] += i;
sort(vec.begin(),vec.end(),comp);
if(!vec.empty())
sol[nod] = vec[0] + 1;
}
int main()
{
fin>>T;
for(int q=1;q<=T;q++)
{
fin>>n;
int a,b;
for(int i=1;i<n;i++)
{
fin>>a>>b;
t[b] = a;
v[a].push_back(b);
v[b].push_back(a);
}
int root = get_root();
dfs(root);
fout<<sol[root]<<'\n';
clear_all();
}
fin.close();
fout.close();
return 0;
}