Cod sursa(job #1524099)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 13 noiembrie 2015 15:57:45
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
#define BUF_SIZE 4096
#define MAXN 100000
int q, pos=BUF_SIZE, lista[MAXN+1], val[2*MAXN-1], next[2*MAXN-1], t[MAXN+1], d[MAXN+1], v[MAXN+1];
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=nextch();
    while(!isdigit(ch)){
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x;
}
inline void adauga(int x, int y){
    q++;
    val[q]=y;
    next[q]=lista[x];
    lista[x]=q;
}
void dfs(int x){
    int p=lista[x], k=0, e=1;
    d[x]=0;
    while(p){
        if(t[x]!=val[p]){
            t[val[p]]=x;
            dfs(val[p]);
        }
        p=next[p];
    }
    p=lista[x];
    while(p){
        if(t[x]!=val[p]){
            v[k++]=d[val[p]];
        }
        p=next[p];
    }
    std::sort(v, v+k);
    for(int i=k-1; i>=0; i--){
        if(d[x]<v[i]+e){
            d[x]=v[i]+e;
        }
        e++;
    }
}
int main(){
    int r, n, x, y, i;
    FILE *fout;
    fin=fopen("zvon.in", "r");
    fout=fopen("zvon.out", "w");
    for(r=read(); r; r--){
        n=read();
        memset(lista, 0, (n+1)*sizeof(int));
        memset(t, 0, (n+1)*sizeof(int));
        q=0;
        for(i=1; i<n; i++){
            x=read();
            y=read();
            adauga(x, y);
            adauga(y, x);
        }
        dfs(1);
        fprintf(fout, "%d\n", d[1]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}