Cod sursa(job #3272889)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 31 ianuarie 2025 13:22:26
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 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,poz;
    if (V[node].size()==1){
        dp1[node]=1;
        dp2[node]=1;
    }
    else {
    for (int num=0;num<V[node].size();num++){
        if (V[node][num]!=father){
            dfs(V[node][num],node);
            dp1[node]=max(dp1[node],dp1[V[node][num]]+1);
            if (dp1[V[node][num]]>maxi1){
                maxi1=dp1[V[node][num]];
                poz=num;
            }
        }
    }
    V[node][poz]=0;
    for (int num=0;num<V[node].size();num++){
        if (V[node][num]!=father){
            if (dp1[V[node][num]]>maxi2){
                maxi2=dp1[V[node][num]];
            }
        }
    }
    V[node][poz]=maxi1;
    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;
}