我们可以将同一颜色的连通块缩成点。
然后我们就得到了一棵黑白相间的树。
树的直径的一半即为答案
ps：树的直径，先从随便一个点出发找到最远的点，再从最远的点走到这个点的最远的点，即为树的直径
#include <bits/stdc++.h>
using namespace std ;
const int MAXN = 200000 + 5 ;
int color[ MAXN ] , fa[ MAXN ] , n ;
struct Node {
int next , to , w ;
} edge[ MAXN << 1 ] ;
int head[ MAXN ] , cnt ;
inline int read () {
int tot = 0 , f = 1 ; char c = getchar () ;
while ( c < '0' || c > '9' ) { if ( c == '-' ) f = -1 ; c = getchar () ; }
while ( c >= '0' && c <= '9' ) { tot = tot * 10 + c - '0' ; c = getchar () ; }
return tot * f ;
}
inline void add ( int x , int y ) {
edge[ ++ cnt ].next = head[ x ] ;
edge[ cnt ].to = y ;
head[ x ] = cnt ;
}
inline int find ( int k ) {
if ( fa[ k ] == k ) return k ;
else return fa[ k ] = find ( fa[ k ] ) ;
}
int maxdeep , maxu ;
inline void dfs ( int deep , int u , int father ) {
if ( deep > maxdeep ) maxdeep = deep , maxu = u ;
for ( int i = head[ u ] ; i ; i = edge[ i ].next ) {
int v = edge[ i ].to ;
if ( v == father ) continue ;
dfs ( deep + 1 , v , u ) ;
}
}
int a[ MAXN ] , b[ MAXN ] ;
signed main () {
n = read () ;
for ( int i = 1 ; i <= n ; i ++ ) {
color[ i ] = read () ;
fa[ i ] = i ;
}
for ( int i = 1 ; i < n ; i ++ ) {
a[ i ] = read () ; b[ i ] = read () ;
int fx = find ( a[ i ] ) , fy = find ( b[ i ] ) ;
if ( color[ fx ] == color[ fy ] ) fa[ fx ] = fa[ fy ] ;
}
for ( int i = 1 ; i <= n ; i ++ )
fa[ i ] = find ( fa[ i ] ) ;
for ( int i = 1 ; i <= n ; i ++ )
if ( fa[ a[ i ] ] != fa[ b[ i ] ] )
add ( fa[ a[ i ] ] , fa[ b[ i ] ] ) , add ( fa[ b[ i ] ] , fa[ a[ i ] ] ) ;
dfs ( 0 , fa[ 1 ] , 0 ) ;
dfs ( 0 , maxu , 0 ) ;
printf ( "%d
" , ( maxdeep + 1 ) / 2 ) ;
}