Cod sursa(job #1977332)

Utilizator retrogradLucian Bicsi retrograd Data 5 mai 2017 10:26:11
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 500000;

int Depth[kMaxN];
vector<int> G[kMaxN];

int DFSDown(int node, int par) {
    int ret = 0;
    if (par != -1) 
        G[node].erase(find(G[node].begin(), G[node].end(), par));
    
    for (auto vec : G[node])
        ret = max(ret, 1 + DFSDown(vec, node));
    
    Depth[node] = ret;
    return ret;
}

void DFSUp(int node, int up) {
    Depth[node] = max(Depth[node], up);

    vector<int> Pref(G[node].size() + 1, -1), 
                Suff(G[node].size() + 1, -1);

    int acc = 0;
    for(int i = 1; i <= G[node].size(); ++i) {
        acc = max(acc, Depth[G[node][i - 1]]);
        Pref[i] = acc;
    }

    acc = 0;
    for (int i = G[node].size(); i >= 1; --i) {
        acc = max(acc, Depth[G[node][i - 1]]);
        Suff[i - 1] = acc;
    }

    for (int i = 0; i < G[node].size(); ++i) {
        DFSUp(G[node][i], max(up + 1, max(Pref[i] + 2, Suff[i + 1] + 2)));
    }
}

int main() {
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    DFSDown(1, -1);
    DFSUp(1, 0);

    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, Depth[i] + 1);
    cout << ans << endl;

    return 0;
}