Cod sursa(job #2822578)

Utilizator andrei81Ragman Andrei andrei81 Data 24 decembrie 2021 13:27:42
Problema Zvon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("zvon.in");
ofstream fout("zvon.out");

void dfs(vector<vector<int>>& G, vector<int>& treesize, int x, int p)
{
    int s = 0;

    for ( int a : G[x] )
        if ( a != p )
        {
            dfs(G, treesize, a, x);
            s += treesize[a];
        }
    treesize[x] = s + 1;
}

void bfs(vector<priority_queue<pair<int, int>>>& G, vector<int>& ftime, int x)
{
    queue<int> Q;

    Q.push(1);
    ftime[1] = 0;

    while ( !Q.empty() )
    {
        x = Q.front();
        Q.pop();

        while ( !G[x].empty() )
        {
            Q.push(G[x].top().second);
            ftime[G[x].top().second] = ftime[x] + 1;
            G[x].pop();
        }
    }
}

void solve()
{
    int n, a, b;
    vector<vector<int>> G;
    vector<int> treesize, ftime;
    vector<priority_queue<pair<int, int>>> G2;

    fin >> n;

    treesize.resize(n + 5);
    ftime.resize(n + 5);
    G.resize(n + 5);
    G2.resize(n + 5);

    for ( int i = 1; i < n; i++ )
    {
        fin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs(G, treesize, 1, 0);

    for ( int i = 1; i < n; i++ )
        for ( int a : G[i] )
            G2[i].push({ treesize[a], a });

    bfs(G2, ftime, 1);

    int maxx = 0;

    for ( int i = 1; i <= n; i++ )
        if ( ftime[i] > maxx )
            maxx = ftime[i];
    fout << maxx << "\n";
}

int main()
{
    int t;
    fin >> t;
    while ( t-- )
        solve();
}