Cod sursa(job #3272888)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 31 ianuarie 2025 13:13:19
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int t,n,i,j,a,b,dp1[100004],dp2[100004];
vector<int>V[100004];
void dfs(int node,int father){
    int maxi1=0,maxi2=0;
    if (V[node].size()==1){
        dp1[node]=1;
        dp2[node]=1;
    }
    else {
    for (int num:V[node]){
        if (num!=father){
            dfs(num,node);
            dp1[node]=max(dp1[node],dp1[num]+1);
            if(!maxi1&&!maxi2){
                maxi1=dp1[num];
            }
            else if (!maxi2){
                maxi2=dp1[num];
                if (maxi2>maxi1)swap(maxi2,maxi1);
            }
            else if(dp1[num]>=maxi1){
                maxi2=maxi1;
                maxi1=dp1[num];
            }
            else if(dp1[num]>=maxi2){
                maxi2=dp1[num];
            }
        }
    }
    dp2[node]=maxi1+maxi2+1;
    }
}
int main()
{   f>>n;
    for (i=1;i<n;i++){
        f>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    int ans=0;
    dfs(1,0);
    for (i=1;i<=n;i++){
        //cout<<dp1[i]<<' ';
        if (ans<dp2[i]){
            ans=dp2[i];
        }
        if (ans<dp1[i]){
            ans=dp1[i];
        }
    }
    g<<ans<<'\n';
    return 0;
}