Cod sursa(job #2725671)

Utilizator preda.andreiPreda Andrei preda.andrei Data 19 martie 2021 14:53:30
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>

using namespace std;

using Tree = vector<vector<int>>;

struct DiameterInfo {
    int diameter;
    int path_to_leaf;
};

DiameterInfo Diameter(const Tree& tree, int root, int father = -1) {
    int son_diameter = 0;
    int long_sons[2] = {};

    for (const auto& other : tree[root]) {
        if (other != father) {
            auto sub = Diameter(tree, other, root);
            son_diameter = max(son_diameter, sub.diameter);

            if (sub.path_to_leaf >= long_sons[0]) {
                long_sons[1] = long_sons[0];
                long_sons[0] = sub.path_to_leaf;
            } else if (sub.path_to_leaf > long_sons[1]) {
                long_sons[1] = sub.path_to_leaf;
            }
        }
    }

    return DiameterInfo {
        .diameter = max(son_diameter, long_sons[0] + 1 + long_sons[1]),
        .path_to_leaf = long_sons[0] + 1,
    };
}

int main() {
    ifstream fin("darb.in");
    ofstream fout("darb.out");

    int nodes;
    fin >> nodes;

    Tree tree(nodes);
    for (auto i = 1; i < nodes; i += 1) {
        int a, b;
        fin >> a >> b;
        tree[a - 1].push_back(b - 1);
        tree[b - 1].push_back(a - 1);
    }

    auto res = Diameter(tree, 0).diameter;
    fout << res << "\n";

    return 0;
}