Cod sursa(job #2045819)

Utilizator danny794Dan Danaila danny794 Data 22 octombrie 2017 21:36:52
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#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;
}