Cod sursa(job #2760928)

Utilizator Catalinu23Gavrila Catalin Catalinu23 Data 29 iunie 2021 16:16:22
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;

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

int n, diam;
vector<int> L[NMAX];
int dp[NMAX]; /// lungimea celui mai lung lant de jos in sus care se termina in i

void dfs(int nod, int t)
{
    int max1=0, max2=0;
    for(auto it: L[nod])
    {
        if(it == t)
            continue;
        dfs(it, nod);
        if(max1<dp[it])
            max2=max1, max1=dp[it];
        else if(max2<dp[it])
            max2=dp[it];
    }
    dp[nod] = max1+1;
    diam = max(diam, max1+max2+1);
}

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

int main()
{
    Citire();
    dfs(1,0);
    fout<<diam;
    return 0;
}