Cod sursa(job #2450371)

Utilizator ejoi2019Ejoi 2019 ejoi2019 Data 22 august 2019 23:21:35
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N=100000+7;
int n;
vector <int> g[N];
int dep[N];
bool vis[N];
int elsker=0;

void dfs(int jeg,int level)
{
        vector <int> dims;
        vis[jeg]=1;
        for(auto &mle : g[jeg])
                if(vis[mle]==0)
                {
                        dfs(mle,level+1);
                        dep[jeg]=max(dep[jeg],dep[mle]);
                        dims.push_back(dep[mle]);
                }
        dep[jeg]++;
        dims.push_back(level);
        dims.push_back(0);
        sort(dims.rbegin(),dims.rend());
        elsker=max(elsker,dims[0]+dims[1]+1);
}



int main()
{
        freopen("darb.in","r",stdin);
        freopen("darb.out","w",stdout);
        scanf("%d",&n);
        for(int i=1;i<n;i++)
        {
                int a,b;
                scanf("%d%d",&a,&b);
                g[a].push_back(b);
                g[b].push_back(a);
        }
        dfs(1,0);
        printf("%d\n",elsker);
        return 0;
}