Cod sursa(job #2917046)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 2 august 2022 20:18:12
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
// This program was written by Mircea Rebengiuc
// on 02.08.2022
// for problem darb

#include <stdio.h>
#include <ctype.h>
#include <vector>

#define MAXN 100000

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch;

  while( !isdigit( ch = fgetc( fin ) ) );
  do
    n = n * 10 + ch - '0';
  while( isdigit( ch = fgetc( fin ) ) );

  return n;
}

std::vector<int> adj[MAXN];
int ans;

static inline int max( int a, int b ){ return a > b ? a : b; }

int dfs( int root, int parrent ){
  int max1 = 0, max2 = 0, nc = 0, depth;

  for( int child : adj[root] )
    if( child != parrent ){
      nc++;

      depth = 1 + dfs( child, root );

      if( depth > max1 ){
        max2 = max1;
        max1 = depth;
      }else if( depth > max2 )
        max2 = depth;
    }

  if( nc >= 2 )
    ans = max( ans, max1 + max2 );
  else if( nc == 1 )
    ans = max( ans, max1 );

  return max1;
}

int main(){
  fin  = fopen( "darb.in",  "r" );
  fout = fopen( "darb.out", "w" );

  int n, i, a, b;
  
  n = fgetint();
  for( i = 1 ; i < n ; i++ ){
    a = fgetint() - 1;
    b = fgetint() - 1;

    adj[a].push_back( b );
    adj[b].push_back( a );
  }

  ans = 0;
  dfs( 0, 0 );

  fprintf( fout, "%d\n", 1 + ans );

  fclose( fin );
  fclose( fout );
  return 0;
}