Cod sursa(job #3272895)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 31 ianuarie 2025 13:46:28
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");

int n, dp1[100004], dp2[100004];
vector<int> V[100004];

void dfs(int node, int father) {
    dp1[node] = 0;
    int maxi1 = 0, maxi2 = 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;  // lungimea maximă până la o frunză
    dp2[node] = maxi1 + maxi2 + 1;  // diametrul trecând prin acest nod
}

int main() {
    f >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        f >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }

    int ans = 0;
    dfs(1, 0);

    for (int i = 1; i <= n; i++) {
        ans = max(ans, max(dp1[i], dp2[i]));
    }

    g << ans << '\n';
    return 0;
}

/*#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;
    if (V[node].size()==1){
        dp1[node]=1;
        dp2[node]=0;
    }
    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;
}
*/