Cod sursa(job #2301912)

Utilizator danielsociuSociu Daniel danielsociu Data 13 decembrie 2018 17:27:41
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
#include <cstring>
std::ifstream cin("darb.in");
std::ofstream cout("darb.out");
#define maxn 100010
inline int max(int a,int b){if(a<b)return b;return a;}
int n;
std::vector<int> g[maxn];

int viz[maxn],SOL,v[maxn];
void dfs(int nod,int lvl){
	viz[nod]=1;
	int max1=0,max2=0;
	for(auto it=g[nod].begin();it!=g[nod].end();++it){
		if(!viz[*it]){
			dfs(*it,lvl+1);
			v[nod]=max(v[nod],v[*it]+1);
			if(max1<v[*it]){
				max2=max1;
				max1=v[*it];
			}
			else
				if(max2<v[*it])
					max2=v[*it];
			if(viz[nod]<viz[*it])
				viz[nod]=viz[*it];
		}
		if(max2!=0)
			SOL=max(SOL,max1+max2+3);
		else
			SOL=max(SOL,max1+1);
	}
}

int main()
{
	int x,y;
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	(v,1,sizeof(v));
	dfs(1,1);
	cout<<SOL;
}