Cod sursa(job #3250039)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 19 octombrie 2024 09:37:02
Problema Diametrul unui arbore Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;

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

vector<int> v[100001];
int d[100001]; // distanta de la al meu la orice leaf din sutreeul lui
int sol = 0;

void dfs(int nod, int f){
    d[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++){
        if(v[nod][i] == f) continue;
        if( d[ v[nod][i] ] == 0 ){
            dfs( v[nod][i], nod );
        }
        d[nod] = max(d[nod], d[ v[nod][i] ] + 1);
    }

    int mx1 = 0, mx2 = 0;
    for(int i = 0; i < v[nod].size(); i++){
        if(v[nod][i] == f) continue;
        if(d[ v[nod][i] ] >= mx1){
            mx2 = mx1;
            mx1 = d[ v[nod][i] ];
        }else if(d[ v[nod][i] ] > mx1){
            mx2 = d[ v[nod][i] ];
        }
    }

    sol = max(sol, mx1 + mx2 + 1);
    // cele doua drumuri + nod
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; in >> n;
    for(int i = 0; i < n - 1; i++){
        int x, y; in >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1, 0);

    out << sol << '\n';

    return 0;
}