Cod sursa(job #2721707)

Utilizator MariusblockMoga Marius-Ioan Mariusblock Data 12 martie 2021 09:51:07
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int> G[100005];
int H[100005];
int n, sol;

void dfs(int nod, int tata){
    int i,vecin, maxim=0,maxim2=0;
    for(i = 0; i < G[nod].size(); i++){
        vecin = G[nod][i];
        if(vecin != tata){
            dfs(vecin, nod);
            H[nod] = max(H[nod],H[vecin]);
            if(H[vecin] >= maxim){
                maxim2 = maxim;
                maxim = H[vecin];
            }else{
                if(H[vecin] > maxim2){
                    maxim2 = H[vecin];
                }
            }
        }
    }
    H[nod]++;
    sol = max(sol,maxim + maxim2 + 1);
}

int main()
{
    int i,a,b;
    fin>>n;
    for(i = 1; i < n; i++){
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,1);
    fout<<sol<<'\n';
    return 0;
}