Pagini recente » infoarena 2 | Cod sursa (job #790110) | Rating Arina Turcu (arinaturcu) | Clasamentul arhivei de probleme | Cod sursa (job #2204922)
#include <fstream>
#include <vector>
#include <list>
using namespace std;
int n, diam;
vector <list <int> > l_ad;
vector <bool> vis;
vector <int> h;
int _dfs(int curr)
{
int deepest = h[curr], max1 = 0, max2 = 0, ld = 0;
vis[curr] = true;
for (int neigh : l_ad[curr])
if (!vis[neigh])
{
h[neigh] = h[curr] + 1;
int low = _dfs(neigh);
if (low > deepest)
deepest = low;
low = low - h[curr];
if (low > max1)
{
if (max1 > max2)
max2 = max1;
max1 = low;
}
else if (low > max2)
max2 = low;
}
ld = max1 + max2;
diam = max(diam, ld);
return deepest;
}
void DFS(int root)
{
vis.resize(n + 1);
h.resize(n + 1);
_dfs(root);
}
int main()
{
ifstream in ("darb.in");
ofstream out ("darb.out");
in >> n;
l_ad.resize(n + 1);
int j, k;
for (int i = 1; i <= n - 1; i++)
{
in >> j >> k;
l_ad[j].push_back(k);
l_ad[k].push_back(j);
}
DFS(1);
out << diam + 1;
in.close();
out.close();
}