自动搬运

查看原文

来自洛谷，原作者为

	暴力出奇迹 OI 好闪，拜谢 OI。

搬运于2025-08-24 21:58:23，当前版本为作者最后更新于2022-02-27 15:42:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

真不懂这题为啥要 LCT，虽然我一开始想的也是 LCT......

结论：一个点 $u$ 在树内的最远点（之一），一定是这棵树的直径的一个端点。

另一个结论：两棵树用一条边连起来的时候，新的直径一定是两棵树各自的直径的两两组合中，最长的那一条。

考虑先离线建出整棵树，倍增维护 LCA，用公式 $dist(u,v)=depth_u+depth_v-2 \times depth_{lca(u,v)}$ 计算两点间距离。

然后按顺序操作，碰到 $\texttt{B}$ 加边操作，合并两棵树，并且我们发现其中一棵只有一个点，那么上面说的四个点两两组合，可以简化为 $3$ 种组合方式，选出距离最大的一种作为新的直径并记录。

碰到 $\texttt{Q}$ 查询操作，直接找到 $k$ 点所在的树的直径，然后分别算出 $k$ 到直径两个端点距离，取较大值即可。

再考虑如何记录直径，我一开始想的是用并查集，把一条直径记录在并查集的代表元的位置。后来想想并查集都不用了，离线建树的过程中，直接求出每个点所在的树的根，把直径记录在根的位置就行了，还省掉了并查集的常数。

时间复杂度：假设操作数是 $q$，结点数是 $n$，如果倍增，预处理复杂度 $O(n \log n)$，单次求 $lca$ 复杂度 $O(\log n)$，总复杂度约为 $O((n+q)\log n)$；用欧拉序列 + ST 表求 $lca$ 的总复杂度 $O(n \log n + q)$，再用四毛子优化就可以做到线性了。

具体细节看代码吧：

#include <cstdio>
using namespace std;
const int N = 100010;
const int LOGN = 17;
struct Edge {
	int to, nxt;
}edges[N];
int point[N][2]; //记录直径的两个端点
int fa[N][LOGN], depth[N];
int opt[N], queryu[N], idx[N];
int head[N], root[N], n, m, nedge; //root[u] 表示 u 点所在的树的根
inline int max(int x, int y) {return x > y ? x : y;}
inline void swap(int &x, int &y) {x ^= y; y ^= x; x ^= y;}
inline void addedge(int u, int v) {
	edges[++nedge].to = v;
	edges[nedge].nxt = head[u];
	head[u] = nedge;
}
inline void dfs(int u) {
	for(register int i = 1; (1 << i) <= depth[u]; ++i)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(register int i = head[u]; i; i = edges[i].nxt) {
		int v = edges[i].to;
		fa[v][0] = u; depth[v] = depth[u] + 1;
		if(u == 0) root[v] = v;
		else root[v] = root[u];
		dfs(v);
	}
}
inline int LCA(int u, int v) {
	if(depth[u] < depth[v]) swap(u, v);
	for(register int i = LOGN - 1; i >= 0; --i)
		if((1 << i) <= depth[u] - depth[v]) u = fa[u][i];
	if(u == v) return u;
	for(register int i = LOGN - 1; i >= 0; --i)
		if(fa[u][i] != fa[v][i]) {u = fa[u][i]; v = fa[v][i];}
	return fa[u][0];
}
inline int dist(int u, int v) {
	return depth[u] + depth[v] - 2 * depth[LCA(u, v)];
}
int main() {
	scanf("%d", &m);
	for(register int i = 1; i <= m; ++i) {
		char op[5];
		scanf("%s %d", op, &queryu[i]);
		if(op[0] == 'B') opt[i] = 1; else opt[i] = 2;
		if(opt[i] == 1) {idx[i] = ++n; addedge(queryu[i] > -1 ? queryu[i] : 0, n);} //idx[i] 记录第 i 步（如果是 B 操作）新建的点的编号
	}
	dfs(0);
	for(register int u = 1; u <= n; ++u) point[u][0] = point[u][1] = u;
	for(register int i = 1; i <= m; ++i) {
		if(opt[i] == 1 && queryu[i] != -1) {
			int x = root[queryu[i]];
			int dist1 = dist(point[x][0], point[x][1]);
			int dist2 = dist(point[x][0], idx[i]), dist3 = dist(point[x][1], idx[i]);
			if(dist1 >= dist2 && dist1 >= dist3) {}
			else if(dist2 >= dist1 && dist2 >= dist3) point[x][1] = idx[i];
			else point[x][0] = idx[i]; //三个距离选最大的记录下来（注意以上的 >= 不能写成 >，具体原因自行思考）
		}
		if(opt[i] == 2) {
			int x = root[queryu[i]];
			printf("%d\n", max(dist(point[x][0], queryu[i]), dist(point[x][1], queryu[i])));
		}
	}
	return 0;
}