Pagini recente » Cod sursa (job #21397) | Cod sursa (job #301885) | Cod sursa (job #2519169) | Monitorul de evaluare | Cod sursa (job #2822593)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
using namespace std;
ifstream fin("zvon.in");
ofstream fout("zvon.out");
int dfs(vector<vector<pair<int, int>>>& G, int x, int p, int& modif)
{
int s = 0;
for ( auto& a : G[x] )
if ( a.second != p )
s += dfs(G, a.second, x, a.first);
modif += s + 1;
return s + 1;
}
int bfs(vector<vector<pair<int, int>>>& G, int x)
{
int y;
queue<pair<int, int>> Q;
bitset<100005> vis;
int maxx = 0;
Q.push({ 0, 1 });
vis[1] = 1;
// time, node
while ( !Q.empty() )
{
x = Q.front().second;
y = Q.front().first;
Q.pop();
for ( auto a : G[x] )
if ( !vis[a.second] )
{
y++;
if ( y > maxx )
maxx = y;
Q.push({ y, a.second });
vis[a.second] = 1;
}
}
return maxx;
}
void solve()
{
// cout << "----------------------------------\n";
int n, a, b;
vector<vector<pair<int, int>>> G;
vector<int> ftime;
fin >> n;
ftime.resize(n + 5);
G.resize(n + 5);
for ( int i = 1; i < n; i++ )
{
fin >> a >> b;
G[a].push_back({ 0,b });
G[b].push_back({ 0,a });
}
int dummy = 0;
dfs(G, 1, 0, dummy);
for ( int i = 1; i < n; i++ )
sort(G[i].begin(), G[i].end(), greater<pair<int, int>>());
// for ( int i = 1; i <= n; i++ )
// {
// cout << "i = " << i << ": ";
// for ( auto a : G[i] )
// cout << "( " << a.first << ", " << a.second << "), ";
// cout << "\n";
// }
fout << bfs(G, 1) << "\n";
}
int main()
{
int t;
fin >> t;
while ( t-- )
solve();
}