Cod sursa(job #1302379)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 26 decembrie 2014 20:49:28
Problema Diametrul unui arbore Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
using namespace std;

const int MAX_N = 100002;

int N;
int maxD[MAX_N];
vector < int > v[MAX_N];
bool vis[MAX_N];

void DFS(int x) {
    vis[x] = 1;

    for(int i = 0; i < (int) v[x].size(); ++i) {
        int y = v[x][i];

        if(vis[y])
            continue;

        DFS(y);
        maxD[x] = max(maxD[x], maxD[y]);
    }

    ++maxD[x];
}

int main() {
    ifstream f("darb.in");
    ofstream g("darb.out");

    f >> N;
    for(int i = 1; i < N; ++i) {
        int x, y;

        f >> x >> y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    DFS(1);

    int ans = 0, p = 0;
    for(int i = 0; i < (int) v[1].size(); ++i) {
        int y = v[1][i];

        if(maxD[y] > maxD[p])
            p = y;
    }

    ans += maxD[p];
    maxD[p] = 0;

    p = 0;
    for(int i = 0; i < (int) v[1].size(); ++i) {
        int y = v[1][i];

        if(maxD[y] > maxD[p])
            p = y;
    }

    ans += maxD[p];
    if(p)
        ++ans;

    g << ans << "\n";

    f.close();
    g.close();

    return 0;
}