Cod sursa(job #2421333)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 14 mai 2019 19:11:27
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
const int M=1<<21,N=100001;
typedef struct
{
    int n,u;
}L;
L g[2*N];
char r[M];
int p,v[N],t[N],d[N],c[N],n,m,a,b,i,s,e;
inline int A()
{
    int a=0;
    for(;r[p]>47;p++)
        a=a*10+r[p]-48;
    p++;
    return a;
}
void B(int x,int y)
{
    g[++m].n=y,g[m].u=v[x],v[x]=m;
}
int C(int o)
{
    memset(t,0,sizeof(t));
    int u,w,i,p=0,y,q;
    for(u=w=1,c[1]=t[o]=o,d[o]=0;u<=w;)
        for(o=c[u++],q=v[o];q;q=g[q].u)
            if(!t[g[q].n])
                y=g[q].n,t[y]=o,d[y]=d[o]+1,c[++w]=y;
    for(i=1;i<=n;++i)
        if(d[i]>d[p])
            p=i;
    return p;
}
int main()
{
    freopen("darb.in","r",stdin),freopen("darb.out","w",stdout),fread(r,M,1,stdin),n=A();
    for(i=1;i<n;++i)
        a=A(),b=A(),B(a,b),B(b,a);
    s=C(1),e=C(s);
    printf("%d",d[e]+1);
    return 0;
}