Cod sursa(job #2794928)

Utilizator cristia_razvanCristia Razvan cristia_razvan Data 5 noiembrie 2021 18:12:32
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define pb push_back

const string filename = "darb";

ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int mxn = 100000;

int ans;
int dp[mxn + 5];
vector<int> m[mxn + 5];


void dfs(int nod, int last)
{
    int max1, max2;
    max1 = max2 = 0;
    for (auto fiu : m[nod])
        if (fiu != last)
        {
            dfs(fiu, nod);
            if (max1 < dp[fiu])
                max2 = max1, max1 = dp[fiu];
            else if (max2 < dp[fiu])
                max2 = dp[fiu];
        }
    dp[nod] = max1 + 1;
    ans = max(ans, max1 + max2 + 1);
}

int main() {

    int n, x, y;

    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> x >> y;
        m[x].pb(y);
        m[y].pb(x);
    }

    dfs(1, 0);
    fout << ans << '\n';
    fin.close();
    fout.close();
    return 0;
}