传送门:【CodeForces】445C Civilization
题目分析:要求每次合并后的连通块内的最长路径最短,那么首先我们要得到合并前的连通块各自内部最长路径的长度L1、L2,然后新的连通块的最长路径一定是max{max{L1,L2},(L1+1)/2+(L2+1)/2+1}。
为什么?合并时取两个连通块最长路径处在最中间的端点合并一定是最优的,合并后的路径一定不会变差。
那么怎么得到一开始所有连通块的长度?首先我们要注意,因为题目一开始就给了固定的几条边,所以一开始所有连通块内部的最长路径是固定长度的!
我们先用并查集预处理出一开始的连通块,同时建立无向边,添加一条边能变成环的不加也一样。处理完以后,从所有连通块的根结点开始做一次dfs,找到离根最远的点,再用这个点做一次dfs,就能找到这个连通块的最长路径了,将路径长度保存在根结点即可。
接下来的步骤就是利用上面的公式就好了。
看到别人用了输入优化跑的比我快,很不开心,也上了输入优化,速度飞快~不小心就跑到第一去了
代码如下:
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REV( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define CLR( a , x ) memset ( a , x , sizeof a ) const int MAXN = 300005 ; const int MAXE = 600005 ; struct Edge { int v , n ; Edge () {} Edge ( int v , int n ) : v ( v ) , n ( n ) {} } E[MAXE] ; int H[MAXN] , cntE ; int p[MAXN] ; int X , length ; int L[MAXN] ; int n , m , q ; int find ( int x ) { return !p[x] ? x : ( p[x] = find ( p[x] ) ) ; } void addedge ( int u , int v ) { E[cntE] = Edge ( v , H[u] ) ; H[u] = cntE ++ ; E[cntE] = Edge ( u , H[v] ) ; H[v] = cntE ++ ; } void dfs ( int u , int fa = -1 , int d = 0 ) { if ( length < d ) { length = d ; X = u ; } for ( int i = H[u] ; i ; i = E[i].n ) if ( E[i].v != fa ) dfs ( E[i].v , u , d + 1 ) ; } void read ( int &x ) { char c ; while ( ( c = getchar () ) < '0' || c > '9' ) ; x = c - '0' ; while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ; } void solve () { int ch , x , y , u , v ; cntE = 1 ; //CLR ( H , 0 ) ; //CLR ( p , 0 ) ; //CLR ( L , 0 ) ; REP ( i , 0 , m ) { read ( u ) , read ( v ) ; x = find ( u ) ; y = find ( v ) ; if ( x != y ) { p[x] = y ; addedge ( u , v ) ; } } FOR ( i , 1 , n ) if ( !p[i] ) { length = -1 ; dfs ( i ) ; length = -1 ; dfs ( X ) ; L[i] = length ; } REP ( i , 0 , q ) { read ( ch ) , read ( x ) ; if ( ch == 1 ) printf ( "%d\n" , L[find ( x )] ) ; else { read ( y ) ; x = find ( x ) ; y = find ( y ) ; if ( x != y ) { p[x] = y ; L[y] = max ( max ( L[x] , L[y] ) , ( L[x] + 1 ) / 2 + ( L[y] + 1 ) / 2 + 1 ) ; } } } } int main () { while ( ~scanf ( "%d%d%d" , &n , &m , &q ) ) solve () ; return 0 ; }