Cod sursa(job #2134616)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 18 februarie 2018 09:57:07
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#define nmax 100005
using namespace std;

FILE *f=fopen("darb.in","r");
FILE *g=fopen("darb.out","w");

vector<int>Q[nmax],lastlvl;
queue<int>que;

int n,cost[nmax],deep[nmax],deepest;
bool viz[nmax];

void read()
{
    fscanf(f,"%d",&n);
    for (int i=1; i<n; ++i)
    {
        int a,b;
        fscanf(f,"%d %d",&a,&b);
        Q[a].push_back(b);
    }
}

void dfs(int nod)
{
    viz[nod]=true;
    int mxd=0,mnd=0;
    bool ok=0;
    for (auto w:Q[nod])
    {
        if (!viz[w])
        {
            ok=1;
            dfs(w);
            cost[nod]=max(cost[nod],cost[w]+1);
            if (deep[w]>mxd)
            {
                mnd=mxd;
                mxd=deep[w];
            }
            else if (deep[w]>mnd)
                mnd=deep[w];

        }
    }
    if (ok==0)
        cost[nod]=deep[nod]=1;
    else if (Q[nod].size()>1)
    {
        deep[nod]=mxd+mnd+1;
        deepest=max(deepest,deep[nod]);
    }
    else
        deep[nod]=cost[nod];
}

void solve()
{
    dfs(1);
    fprintf(g,"%d",deepest);
}

int main()
{
    read();
    solve();
    return 0;
}