Cod sursa(job #2803764)

Utilizator andreimocianAndrei Mocian andreimocian Data 20 noiembrie 2021 13:51:06
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, ans;
int dp[100005];
vector < int > L[100005];

void citire()
{
    int x, y;
    fin >> n;
    for(int i = 1; i < n; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
}

void DFS(int nod, int tata)
{
    int maxx1, maxx2;
    maxx1 = maxx2 = 0;
    for(int i = 0; i < L[nod].size(); i++)
    {
        int fiu = L[nod][i];
        if(fiu != tata)
        {
            DFS(fiu,nod);
            dp[nod] = max(dp[nod],dp[fiu]);
            if(dp[fiu] > maxx1)
            {
                maxx2 = maxx1;
                maxx1 = dp[fiu];
            }
            else if(dp[fiu] > maxx2)
            {
                maxx2 = dp[fiu];
            }
        }
    }
    dp[nod]++;
    ans = maxx1 + maxx2 + 1;
}

int main()
{
    citire();
    DFS(1,0);
    fout << ans;
    return 0;
}