Cod sursa(job #1706659)

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

using namespace std;

const int N = 1e5 + 9;

int n;
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;
}

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