USACO2018FEB P New Barns

「2023zimpha」树的直径练习题

题目传送门

有一棵树，初始没有节点。有 $q$ 次操作，操作分两种：

1. 新建一个节点，将它与 $p$ 节点连接。（若 $p=-1$，则不与其它节点相连 ）
2. 查询在 $k$ 节点所在的连通块中，距它最远的点的距离。

$q \le 10^5$。

树的直径入门题目。

经典结论：树中距离一个节点最远的点一定是直径的两个端点之一。证明见 OI Wiki。

于是我们只需要维护树的直径，先把所有操作离线下来，建出最终的树，倍增求 LCA。新加节点时用两个直径端点到它的距离更新直径即可。

Code

int q, n = 0, p[N], fa[N][20], dep[N];
char op[N];
int dis(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	int X = x, Y = y;
	for (int i = 19; i >= 0; i--) {
		if (fa[X][i] != -1 && dep[fa[X][i]] >= dep[Y]) {
			X = fa[X][i];
		}
	}
	if (X == Y) return dep[x] - dep[X];
	for (int i = 19; i >= 0; i--) {
		if (fa[X][i] != -1 && fa[Y][i] != -1 && fa[X][i] != fa[Y][i]) {
			X = fa[X][i];
			Y = fa[Y][i];
		}
	}
	return dep[x] - dep[X] + dep[y] - dep[Y] + 2;
}
int rt[N], d[N][2], cnt = -1;
void solve() {
	cin >> q;
	rep(i, q) {
		cin >> op[i] >> p[i];
		if (p[i] != -1) p[i]--;
		if (op[i] == 'B') {
			if (p[i] != -1) dep[n] = dep[p[i]] + 1, rt[n] = rt[p[i]];
			else rt[n] = n;
			fa[n++][0] = p[i];
		}
	}
	repp(i, 19) {
		rep(j, n) {
			if (fa[j][i - 1] == -1) fa[j][i] = -1;
			else fa[j][i] = fa[fa[j][i - 1]][i - 1];
		}
	}
	rep(i, q) {
		if (op[i] == 'B') {
			++cnt;
			if (p[i] ==  -1) d[cnt][0] = d[cnt][1] = cnt;
			else {
				int x = d[rt[p[i]]][0], y = d[rt[p[i]]][1];
				if (dis(x, cnt) > dis(d[rt[p[i]]][0], d[rt[p[i]]][1])) {
					d[rt[p[i]]][0] = x;
					d[rt[p[i]]][1] = cnt;
				}
				if (dis(y, cnt) > dis(d[rt[p[i]]][0], d[rt[p[i]]][1])) {
					d[rt[p[i]]][0] = y;
					d[rt[p[i]]][1] = cnt;
				}
			}
		}
		else {
			int x = d[rt[p[i]]][0], y = d[rt[p[i]]][1];
			cout << max(dis(x, p[i]), dis(y, p[i])) << endl;
		}
	}
}