Cod sursa(job #3248613)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 12 octombrie 2024 11:26:18
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;

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

int mx[100001];
vector<int> v[100001];
int n;
int sol = 0;

void dfs(int nod, int p){
    mx[nod] = 1;
    int mx1 = 0, mx2 = 0;
    for(int i = 0; i < v[nod].size(); i++){
        if(v[nod][i] == p) continue;
        dfs( v[nod][i], nod );
        mx[ nod ] = max( mx[nod], mx[ v[nod][i] ] + 1 );
        if(mx[ v[nod][i] ] + 1 >= mx1){
            mx2 = mx1;
            mx1 = mx[ v[nod][i] ];
        }else if(mx[ v[nod][i] ] + 1 > mx2){
            mx2 = mx[ v[nod][i] ];
        }
    }

    sol = max(sol, mx1 + mx2 + 1);
}

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

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

    dfs(1, -1);

    // cout << "mx : ";
    // for(int i = 1; i <= n; i++) cout << mx[i] << " ";
    // cout << '\n';

    out << sol << '\n';
    

    return 0;
}