Cod sursa(job #2709408)

Utilizator ArdeleanOficialAlexandru ArdeleanOficial Data 20 februarie 2021 11:45:16
Problema Revolta Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7, INF = 1e9 + 7;

int dist[N], q[N];
vector < int > adia[N];

int n;

pair < int, int > bfs(int nod) {
    fill(dist, dist + n, INF);
    dist[nod] = 0;
    int st(0), dr(-1), D(0), last(nod);
    q[++dr] = nod;
    while (st <= dr) {
        int x = q[st++];
        D = dist[x];
        last = x;
        for (int i : adia[x])
            if (dist[i] == INF)
                dist[i] = dist[x] + 1, q[++dr] = i;
    }
    return {last, D};
}

int main()
{
    ifstream fin("revolta.in");
    ofstream fout("revolta.out");
    int t;
    fin >> t;
    while (t--) {
        int a, b;
        fin >> n;
        for (int i = 0; i < n; ++i)
            adia[i].clear();
        for (int i = 1; i < n; ++i) {
            fin >> a >> b;
            adia[a].push_back(b);
            adia[b].push_back(a);
        }
        int e = bfs(0).first;
        int d = bfs(e).second;
        fout << (d > 2 ? d / 2 + 1 : d) << '\n';
    }
    return 0;
}