Pagini recente » Cod sursa (job #2367584) | Cod sursa (job #443485) | Monitorul de evaluare | Sport | Cod sursa (job #1260864)
#include <fstream>
#include <vector>
class Arb
{
public:
int id;
std::vector<Arb *> vecs;
};
int solution(const Arb &node, std::vector<int> &dists)
{
dists[node.id] = 0;
if (node.vecs.size() == 0)
{
dists[node.id] = 1;
return 1;
}
int b1 = 0, b2 = 0, ret = 0;
for (int i = 0; i < (int) node.vecs.size(); i++)
{
if (dists[node.vecs[i]->id] == -1)
{
ret = std::max(solution(*node.vecs[i], dists), ret);
if (dists[node.vecs[i]->id] > b1)
b2 = b1, b1 = dists[node.vecs[i]->id];
else if (dists[node.vecs[i]->id] > b2)
b2 = dists[node.vecs[i]->id];
}
}
dists[node.id] = b1 + 1;
return std::max(b1 + b2 + 1, ret);
}
int main()
{
std::ifstream in("darb.in");
std::ofstream out("darb.out");
int n, x, y;
in >> n;
std::vector<Arb> tree(n + 1);
std::vector<int> dists(n + 1, -1);
for (int i = 1; i <= n; i++)
tree[i].id = i;
for (int i = 0; i < n - 1; i++)
{
in >> x >> y;
tree[x].vecs.push_back(&tree[y]);
tree[y].vecs.push_back(&tree[x]);
}
out << solution(tree[1], dists) << '\n';
in.close(), out.close();
}