Pagini recente » Cod sursa (job #377942) | Cod sursa (job #2921788) | Cod sursa (job #882090) | Cod sursa (job #1029775) | Cod sursa (job #2725671)
#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;
}