Cod sursa(job #1317506)

Utilizator retrogradLucian Bicsi retrograd Data 14 ianuarie 2015 22:34:18
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<vector>

#define MAXN 100001

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

vector<int> A[MAXN];
vector<int> G[MAXN];
int MAX1[MAXN], MAX2[MAXN], NEXT1[MAXN], NEXT2[MAXN];
bool VIZ[MAXN];
int n;
int max_d = -1, max_nod = 0;

void depth(int node) {
    for(vector<int>::iterator it=A[node].begin(); it!=A[node].end(); ++it) {
        depth(*it);
        int d = MAX1[*it] + 1;
        if(d > MAX1[node]) {NEXT2[node] = NEXT1[node]; MAX2[node] = MAX1[node]; MAX1[node] = d; NEXT1[node]=*it;}
        else if(d > MAX2[node]) {MAX2[node] = d; NEXT2[node] = *it;}
        if(max_d < MAX1[node] + MAX2[node]) {
            max_d = MAX1[node] + MAX2[node];
            max_nod = node;
        }
    }
}

void dfs(int node) {
    VIZ[node] = 1;
    for(int i=0; i<G[node].size(); i++) {
        if(!VIZ[G[node][i]]) {
            A[node].push_back(G[node][i]);
            dfs(G[node][i]);
        }
    }
}

void writesol(int node) {
    fout<<max_d+1;
}

int main() {
    fin>>n;
    int a, b;
    for(int i=1; i<=n-1; i++) {
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1);
    depth(1);
    writesol(max_nod);
}