Mai intai trebuie sa te autentifici.
Cod sursa(job #2012319)
Utilizator | Data | 18 august 2017 15:04:10 | |
---|---|---|---|
Problema | Diametrul unui arbore | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.06 kb |
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
vector < int > Q[100002];
int n,a,b,v[100002],v2[100002],diametru;
int dfs(int nod,int tata)
{
vector<int>Q2;
for (vector<int>:: iterator it=Q[nod].begin(); it!=Q[nod].end(); ++it)
{
if (*it!=tata)
{
dfs(*it,nod);
Q2.push_back(v[*it]);
}
}
v[nod]=1;
int mx2=0,mx1=0;
for (vector<int>::iterator it=Q2.begin(); it!=Q2.end(); ++it)
if (*it>mx2)
{
swap(mx2,mx1);
mx2=*it;
}
else if (*it>mx1)
mx1=*it;
if (!Q2.empty())
{
Q2.back()=mx2;
v[nod]+=Q2.back();
}
if (Q2.size()>=2)
{
Q2[Q2.size()-2]=mx1;
v2[nod]=1+Q2.back()+Q2[Q2.size()-2];
}
diametru=max(diametru,max(v[nod],v2[nod]));
}
int main()
{
f>>n;
while (f>>a>>b)
{
Q[a].push_back(b);
Q[b].push_back(a);
}
dfs(1,0);
g<<diametru;
return 0;
}