Cod sursa(job #1669194)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 30 martie 2016 14:59:17
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <numeric>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <fstream>
#include <cstdlib>
#include <map>
#define pb push_back
#define mp make_pair
#define INF numeric_limits<int>::max()
#define lsb(x) (-x)&x
#define int64 long long
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
vector< vector<int> > adj;
int n,sol;
int dfs(int x,int p)
{
    int mx1=0,mx2=0;
    for(vector<int>::iterator it=adj[x].begin();it!=adj[x].end();it++)
    if(*it!=p)
    {
        int d=dfs(*it,x);
        if(d>mx1)
        {
            mx2=mx1;
            mx1=d;
        }
        else if(d>mx2)
            mx2=d;
    }
    sol=max(sol,mx1+mx2+1);
    return mx1+1;
}
int main()
{
    in>>n;
    adj=vector< vector<int> > (n+1);
    for(int i=1;i<n;i++)
    {
        int x,y;
        in>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    sol=max(sol,dfs(1,0));
    out<<sol<<'\n';
    return 0;
}