P2195 HXY造公园树的直径 + 并查集

题目描述

现在有一个现成的公园，有 $n$ 个休息点和 $m$ 条双向边连接两个休息点。众所周知， $HXY$ 是一个 $SXBK$ 的强迫症患者，所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作：
$1、$ 对某个休息点 $x$ ，查询公园中可以与个点互相到达的休息点组成的路径中的最长路径。
$2、$ 对于两个休息点 $x、y$ ，如果 $x，y$ 已经可以互相到达则忽略此次操作。否则，在 $x$ 可到达的所有休息点和y可到达的所有休息点（包括 $x，y$ 自身）分别选择一个休息点，然后在这两个休息点之间连一条边，并且这个选择应该满足对于连接后的公园， $x$ 和 $y$ 所在的区域（即 $x，y$ 可达到的所有休息点和边组成的集合）中的最长路径的长度最小。

$HXY$ 打算进行 $q$ 个操作，请你回答她的对于公园情况的询问（操作 $1$ ）或者执行她的操作（操作 $2$ ）。
注：所有边的长度皆为 $1$ 。保证不存在环。最长路径定义为：对于点 $v_1,v_2......v_k$ ，如果对于其中任意的 $v_i$ 和 $v_i+1(1\leq i\leq k-1)$ ，都有边相连接，那么 $v_j(1\leq j\leq k)$ 所在区域的最长路径就是 $k-1$ 。

输入格式

第一行，三个正整数，分别为 $n，m，q$ 。
接下来的 $m$ 行，每一行有两个正整数 $x_i，y_i$ ，表示 $x_i$ 和 $y_i$ 有一条双向边相连。
再接下来的 $q$ 行，每一行表示一个操作。
若该行第一个数为 $1$ ，则表示操作 $1$ ，之后还有一个正整数 $x_i$ ，表示要查询的休息点。

若该行第一个数为 $2$ ，则表示操作 $2$ ，之后还有两个正整数 $x_i，y_i$ ，表示需要执行操作的两个休息点。

输出格式

输出行数为操作 $1$ 的个数。
每行输出对于操作 $1$ 询问的回答。

样例输入1

样例输出1

说明/提示

数据范围：
对于 $10\%$ 的数据，只存在操作 $1$ 。
对于 $30\%$ 的数据， $1\leq m<n\leq 20,1\leq q\leq 5$ 。
对于 $60\%$ 的数据， $1\leq m<n\leq 2000,1\leq q\leq 1000$ 。
对于 $100\%$ 的数据， $1\leq m<n\leq 3*10^5,1\leq q\leq 3*10^5$ 。

题解

树的直径 + 并查集维护树的连通性
首先一遍树形 $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;
}