Cod sursa(job #1847292)

Utilizator SilviuIIon Silviu SilviuI Data 14 ianuarie 2017 14:55:24
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define nmax 100010

using namespace std;

int n, a, b, sol;
int dp[nmax];
vector <int> g[nmax];

void dfs(int nod, int dad)
{
    vector <int> ans;

    for (int i = 0; i < (int)g[nod].size(); i++)
        if (g[nod][i] != dad) {
            dfs(g[nod][i], nod);
            dp[nod] = max(dp[nod], dp[g[nod][i]] + 1);
    }

    for (int i = 0; i < (int)g[nod].size(); i++)
        if (g[nod][i] != dad) ans.push_back(dp[g[nod][i]]);

    sort(ans.begin(), ans.end());
    reverse(ans.begin(), ans.end());

    if (ans.size() > 1) sol = max(sol, ans[0] + ans[1] + 1); else
        if (ans.size() == 1) sol = max(sol, ans[0] + 1);
}

int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) dp[i] = 1;

    for (int i = 1; i < n; i++) {

        scanf("%d %d", &a, &b);

        g[a].push_back(b);
        g[b].push_back(a);

    }

    dfs(1, 0);

    printf("%d", sol);

    return 0;
}