Cod sursa(job #2615197)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 13 mai 2020 20:11:46
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
using VI  = vector<int>;
using VVI = vector<VI>;
const string problem("darb");
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");
const int inf(1e9);
int n, x, y, dmax;
VVI g;
VI d;
inline void DFS(int x, int dad) {
    int y, w, d1(0), d2(0), curr(0);
    for (const int& y : g[x]) {
        if (y != dad) {
            DFS(y, x);
            curr = d[y] + 1;
            d[x] = max(d[x], curr);
            if (d1 <= curr)
                d2 = d1, d1 = curr;
            else if (d2 < curr)
                d2 = curr;
        }
    }
    dmax = max(dmax, d1 + d2);
}
int main() {
    DAU
    fin >> n;
    g = VVI(n + 1);
    for (int i = 1; i < n; ++i) {
        fin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    d = VI(n + 1);
    DFS(1, -1);
    fout << dmax + 1;
    PLEC
}