Cod sursa(job #1612631)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 24 februarie 2016 22:51:34
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#define MAXN 100000
int ans, k, lista[MAXN+1], next[2*MAXN-1], val[2*MAXN-1], t[MAXN+1], hmax[MAXN+1], h[MAXN+1];
inline void adauga(int x, int y){
    k++;
    val[k]=y;
    next[k]=lista[x];
    lista[x]=k;
}
void dfs(int x){
    int p=lista[x];
    hmax[x]=h[x];
    while(p){
        if(t[x]!=val[p]){
            t[val[p]]=x;
            h[val[p]]=h[x]+1;
            dfs(val[p]);
            if(ans<hmax[x]-h[x]+hmax[val[p]]-h[x]){
                ans=hmax[x]-h[x]+hmax[val[p]]-h[x];
            }
            if(hmax[x]<hmax[val[p]]){
                hmax[x]=hmax[val[p]];
            }
        }
        p=next[p];
    }
}
int main(){
    int n, x, y, i;
    FILE *fin, *fout;
    fin=fopen("darb.in", "r");
    fout=fopen("darb.out", "w");
    fscanf(fin, "%d", &n);
    for(i=1; i<n; i++){
        fscanf(fin, "%d%d", &x, &y);
        adauga(x, y);
        adauga(y, x);
    }
    dfs(1);
    fprintf(fout, "%d\n", ans+1);
    fclose(fin);
    fclose(fout);
    return 0;
}