Cod sursa(job #2308769)

Utilizator al3xionescuIonescu Alexandru al3xionescu Data 27 decembrie 2018 18:42:48
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bitset>
#include <fstream>
#include <vector>
#include <utility>
std::ifstream cin("darb.in");
std::ofstream cout("darb.out");
int n, x, y;
std::vector<std::vector<int>> children;
std::bitset<100001> visited;
std::pair<int, int> solve(int node) {
    visited[node] = true;
    std::pair<int, int> childSolution(1, 1), solution(1, 0);
    for (const auto& child : children[node]) {
        if (visited[child]) {
            continue;
        }
        childSolution = solve(child);
        solution.first = std::max(solution.first, childSolution.first);
        solution.first = std::max(solution.first, solution.second + childSolution.second + 1);
        solution.second = std::max(solution.second, childSolution.second);
    }
    solution.second++;
    return solution;
}
int main() {
    cin >> n;
    children.resize(n + 1);
    for (int i = 1; i < n; i++) {
        cin >> x >> y;
        children[x].emplace_back(y);
        children[y].emplace_back(x);
    }
    cout << solve(1).first;
    return 0;
}