Cod sursa(job #3272898)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 31 ianuarie 2025 13:55:25
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int t,n,i,j,a,b,dp1[200004],dp2[200004];
vector<int>V[200004];
void dfs(int node,int father){
    int maxi1=0,maxi2=0,poz=0;
    for (int num : V[node]) {
        if (num != father) {
            dfs(num, node);
            if (dp1[num]>maxi1){
                maxi2=maxi1;
                maxi1=dp1[num];
            }
            else if (dp1[num]>maxi2){
                maxi2=dp1[num];
            }
        }
    }
    dp1[node]=maxi1+1;
    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;
}