# CFR 455 C. Civilization ( UnionFind )

Problem - C - Codeforces

O( N lg N + Q lg N )

```struct UF{
vi fa, dmt; // diameter
UF( int sz ){
fa = dmt = vi( sz );
for( int i = 0; i < sz; ++i )
fa[ i ] = i;
}
int find( int x ){
return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
}
int unite( int x, int y ){
int a = find( x );
int b = find( y );
if( a == b )
return 0;
dmt[ a ] = max( { dmt[ a ], dmt[ b ], ( dmt[ a ] + 1 ) / 2 + ( dmt[ b ] + 1 ) / 2 + 1 } );
fa[ b ] = a;
return 1;
}
};

int N, M, Q;
vp edge;

void init(){
cin >> N >> M >> Q;
edge = vp( M );
for( int i = 0; i < M; ++i )
cin >> edge[ i ].first >> edge[ i ].second;
}

vvi iG; // initial graph
UF *uf;

int get_dmt( int u ){ // get diamater of tree that contains u
static vi vis( N );
int t;
queue< int > que;
que.emplace( u );
vis[ u ] = 1;
while( not que.empty() ){
int x = que.front();
que.pop();
t = x;
for( int y : iG[ x ] )
if( not vis[ y ] )
vis[ y ] = 1,
que.emplace( y );
}
swap( u, t ); // u : end of a furthest point

static vi vis_( N );
int res;
queue< pii > d_x;
d_x.emplace( 0, u );
vis_[ u ] = 1;
while( not d_x.empty() ){
int d, x; tie( d, x ) = d_x.front(); d_x.pop();
res = d;
for( int y : iG[ x ] )
if( not vis_[ y ] )
vis_[ y ] = 1,
d_x.emplace( d + 1, y );
}

return res;
}

void preprocess(){
uf = new UF( N );
iG = vvi( N );
for( int i = 0; i < M; ++i )
iG[ edge[ i ].first - 1 ].emplace_back( edge[ i ].second - 1 ),
iG[ edge[ i ].second - 1 ].emplace_back( edge[ i ].first - 1 ),
uf->unite( edge[ i ].first - 1, edge[ i ].second - 1 );
for( int i = 0; i < N; ++i )
if( uf->find( i ) == i )
uf->dmt[ i ] = get_dmt( i );
}

void solve(){
for( int i = 0; i < Q; ++i ){
int op; cin >> op;
if( op == 1 ){
int x; cin >> x; --x;
cout << uf->dmt[ uf->find( x ) ] << endl;
} else{
int x, y; cin >> x >> y; --x, --y;
uf->unite( x, y );
}
}
}
```