Cod sursa(job #2953459)

Utilizator AswVwsACamburu Luca AswVwsA Data 11 decembrie 2022 14:53:58
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 100004;

vector <int> g[NMAX];
vector <int> children[NMAX];
int d[NMAX];
int mxd[NMAX];
bool viz[NMAX];

void dfs(int nod)
{
    viz[nod] = 1;
    mxd[nod] = d[nod];
    for (int u : g[nod])
        if (!viz[u])
        {
            children[nod].push_back(u);
            d[u] = d[nod] + 1;
            dfs(u);
            mxd[nod] = max(mxd[u], mxd[nod]);
        }
}
int main()
{
    ifstream cin("darb.in");
    ofstream cout("darb.out");
    int n, i;
    cin >> n;
    for (i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1);
    int ans = 0;
    for (i = 1; i <= n; i++)
    {
        int mx1, mx2;
        mx1 = mx2 = 0;
        for (int u : children[i])
            if (mx1 <= mxd[u])
            {
                mx2 = mx1;
                mx1 = mxd[u];
            }
            else
                mx2 = max(mx2, mxd[u]);
        ans = max(ans, mx1 + mx2 - 2 * d[i]);
    }
    cout << ans + 1;
}