Cod sursa(job #1244510)

Utilizator AndreyPAndrei Poenaru AndreyP Data 17 octombrie 2014 17:59:10
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bitset>
#include <cstdio>
#include <vector>
using namespace std;

#define N_MAX 100010

int N;
vector<int> g[N_MAX];
int depth[N_MAX];
bitset<N_MAX> vis;

inline void read() {
    scanf("%d", &N);

    int x, y;
    for (int i = 1; i < N; ++i) {
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

int dfs(int node) {
    int best1 = 0;
    int best2 = 0;
    int res = 0;
    int childRes;

    vis[node] = true;

    for (size_t i = 0, lim = g[node].size(); i < lim; ++i) {
        if (vis[g[node][i]]) {
            continue;
        }

        childRes = dfs(g[node][i]);

        if (depth[g[node][i]] > best1) {
            best2 = best1;
            best1 = depth[g[node][i]];
        } else
        if (depth[g[node][i]] > best2) {
            best2 = depth[g[node][i]];
        }

        if (childRes > res) {
            res = childRes;
        }
    }

    depth[node] = best1 + 1;

    if (best1 + 1 + best2 > res) {
        res = best1 + 1 + best2;
    }

    return res;
}

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

    read();
    printf("%d\n", dfs(1));

    return 0;
}