Cod sursa(job #2481000)

Utilizator Moldovan_Andrei112002Moldovan Andrei Moldovan_Andrei112002 Data 26 octombrie 2019 12:44:14
Problema Diametrul unui arbore Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");ofstream fout("darb.out");
vector<int>vecini[10005];
int raspuns[10005],lant[10005],n;

void dfs(int nodcrt,int parinte)
{
    int maxx1=0,maxx2=0;
    lant[nodcrt]=1;
    raspuns[nodcrt]=1;
    for(int i=0;i<vecini[nodcrt].size();i++)
    {
        int nodurm=vecini[nodcrt][i];
        if(nodurm!=parinte)
        {
            dfs(nodurm,nodcrt);
            lant[nodcrt]=max(lant[nodcrt],lant[nodurm]+1);
            raspuns[nodcrt]=max(raspuns[nodcrt],raspuns[nodurm]);
            if(lant[nodurm]>maxx1)
            {
                maxx2=maxx1;
                maxx1=lant[nodurm];
            }else
            {
                if(lant[nodurm]>maxx2)
                {
                    maxx2=lant[nodurm];
                }
            }
        }
    }
    raspuns[nodcrt]=max(raspuns[nodcrt],maxx1+maxx2+1);
}
int main()
{
    fin>>n;
    int i;
    for(i=1;i<n;i++)
    {
        int a,b;
        fin>>a>>b;
        vecini[a].push_back(b);
        vecini[b].push_back(a);
    }
    dfs(1,-1);
    fout<<raspuns[1];

    fin.close();fout.close();
    return 0;
}