Cod sursa(job #2915528)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 23 iulie 2022 01:11:22
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");
const int NMAX=100005;

///dist[i]=lungimea lantului maxim care se termina in nodul i din subgraful determinat de acesta
int N, sol, dist[NMAX];
vector<int> g[NMAX];

void dfs(int nod, int tata){
    int mx1=0, mx2=0;
    for(auto x: g[nod]){
        if(x==tata)
            continue;
        dfs(x,nod);
        if(dist[x]>=mx1){
            mx2=mx1;
            mx1=dist[x];
        }
        else if(dist[x]>mx2)
            mx2=dist[x];
    }
    sol=max(sol,mx1+mx2+1);
    dist[nod]=mx1+1;
}

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

    dfs(1,0);

    fout<<sol;

    fin.close();
    fout.close();
    return 0;
}