Cod sursa(job #2886493)

Utilizator popescuadrianpopescuadrian popescuadrian Data 7 aprilie 2022 20:15:48
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream cin("darb.in");
ofstream cout("darb.out");
vector<int>adj[200005];
int biggest[200005];
int maxim=0;
int dfs(int curr,int par)
{
    int i,k,second=0;
    for(i=0;i<adj[curr].size();i++)
    {
        k=adj[curr][i];
        if(k!=par)
        {
            dfs(k,curr);
            if(biggest[k]+1>=biggest[curr])
            {
                second=biggest[curr];
                biggest[curr]=biggest[k]+1;
            }
            else if(biggest[k]+1>second)
            {
                second=biggest[k]+1;
            }
        }
    }
    maxim=max(maxim,biggest[curr]+second-1);
    maxim=max(maxim,biggest[curr]);
    if(adj[curr].size()==1 && curr!=1)
    {
        biggest[curr]=1;
    }
}
int main()
{
    int n,i,j,a,b;
    cin>>n;
    for(i=1;i<n;i++)
    {
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,0);
    cout<<maxim;
    return 0;
}