Cod sursa(job #2480907)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 26 octombrie 2019 11:03:26
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector<int> vecini[100005];

int raspuns[100005];
int lant[1000005];
int n;

void dfs(int nod_curent, int parinte)
{
    /// dfs (nodul_curent) va fi apelat o singura data pentru ca are un singur parinte deci nu avem nevoie de verificare

    int maxi1 = 0, maxi2 = 0;
    lant[nod_curent] = 1; /// nodul in sine poate forma un lant ce contine doar nodul curent
    raspuns[nod_curent] = 1;
    for(int i = 0; i < vecini[nod_curent].size(); i++)
    {
        int nod_urmator = vecini[nod_curent][i];
        if(nod_urmator != parinte) /// nu apelam dfs in parinte garantand astfel ca fiecare nod va intra in functia dfs o singura data
        {
            dfs(nod_urmator, nod_curent);
            lant[nod_curent] = max(lant[nod_curent], lant[nod_urmator] + 1); /// calculam cel mai lung lant care se termina in nodul curent
            raspuns[nod_curent] = max(raspuns[nod_curent], raspuns[nod_urmator]); /// raspuns curent e maximul dintre raspunsurile fiilor

            if(lant[nod_urmator] > maxi1) /// gasim cele mai bune 2 lanturi pentru a vedea daca putem gasi un raspuns mai bun
            {
                maxi2 = maxi1;
                maxi1 = lant[nod_urmator];
            }
            else if(lant[nod_urmator] > maxi2)
            {
                maxi2 = lant[nod_urmator];
            }
        }
    }
    raspuns[nod_curent] = max(raspuns[nod_curent], maxi1 + maxi2 + 1); /// incercam sa unim cele 2 lanturi pentru a forma o solutie
                                                                /// (2 lanturi disjuncte se pot unii la capete si formeaza tot un lant)
}

int main()
{
    fin >> n;
    for(int i = 1; i < n; i++)
    {
        int a,b;
        fin >> a >> b;
        vecini[a].push_back(b);
        vecini[b].push_back(a);
    }

    dfs(1, -1);
    fout << raspuns[1];  /// numarul de noduri din lant
    return 0;
}