Cod sursa(job #2670677)

Utilizator Harsa_AndreiHarsa Andrei Harsa_Andrei Data 10 noiembrie 2020 14:57:58
Problema Diametrul unui arbore Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

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

bool notfr[100002];
int d[100002];
int t[100002];

int DIST(int i)
{
    if(d[i] == 0 && t[i] != 0)
        d[i] = DIST(t[i]) + 1;
    return d[i];
}

int main()
{
    int n, x, y, max1 = -1, max2 = -1;

    fin >> n;

    for(int i = 1; i < n; i++)
    {
        fin >> x >> y;
        t[y] = x;
        notfr[x] = true;
    }

    for(int i = 1; i <= n; i++)
    {
        int dist = DIST(i);
        if(!notfr[i])
        {
            if(dist > max1)
            {
                max2 = max1;
                max1 = dist;
            }
            else if(dist > max2)
                max2 = dist;
        }
    }

    fout << max1 + max2 + 1;
    return 0;
}