Cod sursa(job #2822593)

Utilizator andrei81Ragman Andrei andrei81 Data 24 decembrie 2021 14:15:30
Problema Zvon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#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();
}