Cod sursa(job #1706662)

Utilizator lflorin29Florin Laiu lflorin29 Data 22 mai 2016 22:31:56
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 9;

int n, ans;
int d[N][2];
vector<int>g[N];

void read() {
    freopen("darb.in", "r", stdin);
    scanf("%d", &n);
    for(int i = 1, x, y; i < n; ++i) {
        scanf("%d %d", &x, &y);
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void dfs(int nod, int tata) {
    int mx1 = 0, mx2 = 0;
    for(const auto& it: g[nod]) {
       if(it != tata) {
          dfs(it, nod);
          if(d[it][0] > mx1)
             mx2 = mx1, mx1 = d[it][0];
          else
            if(d[it][0] > mx2) mx2 = d[it][0];
       }
    }

    d[nod][0] = mx1 + 1, d[nod][1] = mx1 + mx2 + 1;
    ans = max(ans, d[nod][1]);
}

int main() {
    read();
    dfs(0, -1);
    freopen("darb.out", "w", stdout);
    printf("%d", ans);
    return 0;
}