Pagini recente » Cod sursa (job #2567584) | Cod sursa (job #296469) | Monitorul de evaluare | Cod sursa (job #1001853) | Cod sursa (job #1584976)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int Mn = 1e5 + 6;
int n,pos = 0;
int dp[Mn];
char buff[Mn];
vector< int > g[Mn];
void read(int &num)
{
num = 0;
char sign = '+';
while (!isdigit(buff[pos]))
{
sign = buff[pos];
if (++pos == Mn)
fread(buff,1,Mn,stdin),pos = 0;
}
while (isdigit(buff[pos]))
{
num = num * 10 + buff[pos] - '0';
if (++pos == Mn)
fread(buff,1,Mn,stdin),pos = 0;
}
if (sign == '-')
num *= -1;
}
bool comp(int a,int b)
{
return (dp[a] > dp[b]);
}
int dfs(int node,int parent)
{
if (g[node].size() == 0)
return 0;
for (int it = 0;it < g[node].size();it++)
if (g[node][it] != parent)
dp[g[node][it]] = dfs(g[node][it],node);
sort(g[node].begin(),g[node].end(),comp);
dp[node] = 0;
bool b = 1;
for (int it = 0;it < g[node].size();it++)
if (dp[node] < dp[g[node][it]] + it + b && g[node][it] != parent)
dp[node] = dp[g[node][it]] + it + b;
else
if (g[node][it] == parent)
b = 0;
return dp[node];
}
int main()
{
freopen("zvon.in","r",stdin);
freopen("zvon.out","w",stdout);
int t;
read(t);
for (;t;t--)
{
read(n);
for (int i = 1;i <= n;i++)
g[i].clear();
for (int i = 1;i < n;i++)
{
int x,y;
read(x);
read(y);
g[x].push_back(y);
g[y].push_back(x);
}
printf("%d\n",dfs(1,0));
}
return 0;
}