Cod sursa(job #3194038)

Utilizator Mihai_999Diaconeasa Mihai Mihai_999 Data 16 ianuarie 2024 18:54:54
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'

using namespace std;

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

const int NMAX = 1e5+1;
int n, fr[NMAX], ans;
vector<int> adj[NMAX];

int dfs(int x)
{
    int max1 = 0, max2 = 0;
    fr[x] = 1;
    for (int i : adj[x])
    {
        if (!fr[i])
        {
            int l = dfs(i);
            if (l >= max2)
            {
                max1 = max2;
                max2 = l;
            }
            else if (l > max1)
                max1 = l;
        }
    }
    ans = max(ans, max1+max2+1);
    return max2+1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    fout << ans;
    return 0;
}