Pagini recente » Cod sursa (job #396205) | Cod sursa (job #259180) | Cod sursa (job #763811) | Cod sursa (job #491960) | Cod sursa (job #1198522)
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#define N 100001
std::vector<std::vector<int> >g(N);
std::vector<bool> viz(N);
std::pair<int,int> dfs(int k) // (lant, belt)
{
viz[k]=true;
int maxlant1=-1, maxlant2=-1, maxbelt=0;
int lant, belt;
for(int i=0;i<g[k].size();i++)
{
int node = g[k][i];
if(viz[node]==false)
{
std::pair<int,int> p=dfs(node);
lant = p.first;
belt = p.second;
if(lant>maxlant2)
{
maxlant1=maxlant2;
maxlant2=lant;
}
else if(lant>maxlant1)
{
maxlant1=lant;
}
if(belt>maxbelt)
{
maxbelt=belt;
}
}
}
std::pair<int, int> ret = std::make_pair(maxlant2+1, std::max(2+maxlant1+maxlant2,maxbelt));
return ret;
}
int main ()
{
std::ifstream fin("darb.in");
std::ofstream fout("darb.out");
int n,a,b;
fin>>n;
g.resize(n+1);
for(int i=1;i<n;i++)
{
fin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
std::pair<int,int> ret = dfs(1);
fout<<std::max(ret.first, ret.second)+1;
return 0;
}