CF455C Civilization 树的直径 + 并查集

题意翻译

给出一个由 $n$ 个点， $m$ 条边组成的森林，有 $q$ 组询问
$1.$ 给出点 $x$ ，输出点 $x$ 所在的树的直径
$2.$ 给出点 $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$ 的个数
每行一个整数表示对应的操作一的答案

说明与提示

$1≤m<n≤3*10^5$
$1≤q≤3*10^5$
感谢 @_Wolverine 提供的翻译

样例输入

样例输出

题解

树的直径 + 并查集维护树的连通性
首先一遍树形 $DP$ ，求出每个并查集代表元素 $x$ 所在树的直径 $c[x]$
考虑合并两个树，假设这两棵树的连接点为 $x,y$ ，代表元素分别为 $fx,fy$
则合并后的最小直径为 $max((c[fx]+1)/2+(c[fy]+1)/2,max(c[fx], c[fy]))$
并查集维护即可

code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e5 + 5;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch^48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
struct Edge {
	int to;
	Edge *nxt;
	Edge(int to, Edge *nxt) : to(to), nxt(nxt) {}
} *head[N];
void add(int x, int y) {head[x] = new Edge(y, head[x]);}
int n, m, q, len, fa[N], c[N], g[N], d[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void dfs(int x, int f) {
	int m1 = 0, m2 = 0;
	for(Edge *i = head[x]; i; i = i->nxt) {
		if(i->to == f) continue; dfs(i->to, x);
		int tmp = d[i->to] + 1;
		d[x] = max(d[x], tmp);
		if(tmp > m1) m2 = m1, m1 = tmp;
		else if(tmp > m2) m2 = tmp;
	}
	g[x] = m1 + m2; len = max(len, g[x]);
}
void calc(int x) {len = 0; dfs(x, 0); c[x] = len;}
int main() {
	n = read(); m = read(); q = read();
	for(int i = 1; i <= n; ++ i) fa[i] = i;
	for(int i = 1, x, y; i <= m; ++ i) x = read(), y = read(), add(x, y), add(y, x), fa[find(x)] = find(y);
	for(int i = 1; i <= n; ++ i) if(fa[i] == i) calc(i);
	for(int i = 1, opt, x, y; i <= q; ++ i) {
		opt = read(); x = read();
		if(opt == 1) {printf("%d\n", c[find(x)]); continue;}
		y = read(); x = find(x); y = find(y);
		if(x == y) continue;
		int tmp = max((c[x] + 1) / 2 + (c[y] + 1) / 2 + 1, max(c[x], c[y]));
		fa[find(x)] = find(y); c[find(x)] = tmp;
	}
	return 0;
}