Cod sursa(job #3196080)

Utilizator AswVwsACamburu Luca AswVwsA Data 22 ianuarie 2024 18:50:41
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <vector>
#define ll long long
using namespace std;

const int NMAX = 1e5;

vector <int> g[NMAX + 1];

int d[NMAX + 1];

int ans;

pair <int, int> dfs(int nod, int parent)
{
    d[nod] = d[parent] + 1;

    pair <int, int> dia(-1, -1);
    for (int x : g[nod])
        if (x != parent)
        {
            pair <int, int> ceva = dfs(x, nod);
            if (dia.first == -1)
                dia = ceva;
            else
            {
                pair <int, int> aux;
                int dist = d[dia.first] + d[ceva.first] - 2 * d[nod];
                if (dist > ans)
                {
                    ans = dist;
                    aux = {dia.first, ceva.first};
                }
                dist = d[dia.first] + d[ceva.second] - 2 * d[nod];
                if (dist > ans)
                {
                    ans = dist;
                    aux = {dia.first, ceva.second};
                }
                dist = d[dia.second] + d[ceva.first] - 2 * d[nod];
                if (dist > ans)
                {
                    ans = dist;
                    aux = {dia.second, ceva.first};
                }
                dist = d[dia.second] + d[ceva.second] - 2 * d[nod];
                if (dist > ans)
                {
                    ans = dist;
                    aux = {dia.second, ceva.second};
                }
                dia = aux;
            }
        }
    if (dia.first == -1)
        dia = {nod, nod};
    return dia;
}

signed main()
{
    ifstream cin("darb.in");
    ofstream cout("darb.out");
    int n, i;
    cin >> n;
    for (i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 0);
    cout << ans + 1;
}