CF455C Civilization

题意翻译

给出一个由 n 个点，m 条边组成的森林，有 q 组询问

给出点 x，输出点 x所在的树的直径
给出点 x,y，（如果 x,y在同一棵树中则忽略此操作）选择任意两点 u,v，使得 u 跟 x 在同一棵树中且 v 跟 y 在同一棵树中。将 u,v 之间连一条边，使得连边后的到的新树的直径最小
输入格式
第一行三个整数 n,m,q，分别表示点的个数，边的个数和询问个数
接下来 m 行，每行两个整数 x,y，表示有一条链接点 x,y 的边
接下来 q 行，每行表示一条操作
操作1：1 x
操作2：2 x y

输出格式

输出行数为操作1的个数
每行一个整数表示对应的操作一的答案

说明与提示

(n , m , q <= 3 imes 10 ^ 5)
感谢 @_Wolverine 提供的翻译

输入输出样例

输入

6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3
1 1

输出

贪心+并查集。
若有两个连通块x,y它们的直径分别是(c[x] , c[y]) 那么这两个连通块合并之后的直径是(max(c[x] , c[y] , frac{c[x]+1}{2} + frac{c[y]+1}{2} +1))
也就是说会选取两个连通块的中点。
正确性，假设不选直径的中点，比如x的连通块选了t这个点那么到直径的距离+直径的一段才是要加的东西，仔细想想这个比直径的一半要大。。(意会。。)
剩下的就简单了，用并查集维护即可。

写的时候没有注意联通了就不用连边了，导致c数组和自己又算了一遍，光荣的WA了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
using namespace std;
const int N = 3e5+10;
inline int read()
{
    register int x = 0 , f = 0; register char c = getchar();
    while(c < '0' || c > '9') f |= c == '-' , c = getchar();
    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
    return f ? -x : x;
}
int n , m , q , cnt , ans;
int head[N] , vis[N] , c[N] , fa[N] , f[N];
struct edge{ int v , nex; }e[N << 1];
inline void add(int u , int v) { e[++cnt].v = v; e[cnt].nex = head[u]; head[u] = cnt; return ; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void dfs(int x)
{
	vis[x] = 1;
	for(int i = head[x] , v; i ; i = e[i].nex)
	{
		v = e[i].v; if(vis[v]) continue; dfs(v);
		ans = max(ans , f[x] + f[v] + 1); f[x] = max(f[x] , f[v] + 1);
	}
	return ;
}

int main()
{
	n = read(); m = read(); q = read();
	for(int i = 1 ; i <= n ; ++i) fa[i] = i;
	for(int i = 1 , u , v; i <= m ; ++i) u = read() , v = read() , add(u , v) , add(v , u) , fa[find(u)] = find(v);
	for(int i = 1 ; i <= n ; ++i) if(!vis[i]) ans = 0 , dfs(i) , c[find(i)] = ans;
//	for(int i = 1 ; i <= n ; ++i) cout << c[i] << ' '; cout << '
';
	int op , x , y;
	while(q--)
	{
		op = read(); x = read();
		if(op == 1) cout << c[find(x)] << '
';
		else
		{
			y = read() , x = find(x) , y = find(y); if(x == y) continue; // @@@
			fa[x] = y , c[y] = max((c[x] + 1) / 2 + (c[y] + 1) / 2 + 1 , max(c[x] , c[y]));
		}
	}
	return 0;
}
/*
6 5 2
1 2
2 3
3 4
3 5
5 6
*/