题解：P4810 [COCI 2014/2015 #3] STOGOVI

校内 T4，打了个神秘树剖跑路了。

主要思路都是一样的，维护每一个版本的栈顶

top_i

，那么分别对于每个操作进行一些修改。

a 操作，直接将 $top_i = i$ ；
b 操作，相当于要询问父亲的父亲的栈顶，也就是 $fa_{top_v}$ ，删掉了 $top_v$ 。
c 操作，相当于不做任何操作， $top_i = top_v$ ，答案就是 lca 的深度， $dep_{LCA(top_v, top_w)}$ 。

Q：为什么用栈顶元素做这些操作？

\\

A：由于删除操作的存在。如果直接用编号的话，可能就把删除忽略掉，导致答案错误。

Q：为什么只在加元素时维护这些数组？

\\

A：不难发现，每一个版本的栈顶元素

top_i

都是在一次 a 操作后被加进来的，所以每一个节点都可以回溯到一个最近的 a 操作。而我们关联答案也只需要

top_i

，所以我们只需维护 a 操作的数组即可。

如果你想，你也可以对于每个操作维护一次。

主要思路就这样，实现方式有很多种，这里只给最简单的倍增不建图了。

CPP

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5, M = 20 + 5;
int n, top[N], dep[N], fa[N][M], lg[N];

int lca (int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) return x;

    for (int i = lg[dep[x]] - 1; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int main () {

	ios::sync_with_stdio (false);
	cin.tie (0); cout.tie (0);
	
	cin >> n;
	for (int i = 1; i <= n; ++i) lg[i] = lg[i-1] + (1 << lg[i-1] == i);
	for (int i = 1; i <= n; ++i) {
		char opt; int v;
		cin >> opt >> v;
		if (opt == 'a') {
			// 直接在加元素的时候维护 
			dep[i] = dep[top[v]] + 1;
			top[i] = i;
			fa[i][0] = top[v];
			for (int j = 1; j <= 19; ++j) fa[i][j] = fa[fa[i][j - 1]][j - 1];
		} else if (opt == 'b') {
			top[i] = fa[top[v]][0];
			cout << top[v] << '\n';
		} else {
			int w;
			cin >> w;
			top[i] = top[v];
			cout << dep[lca (top[v], top[w])] << '\n';
		}
	}
	
	return 0;
}

题解：P4810 [COCI 2014/2015 #3] STOGOVI

文章操作

相关推荐

评论

题解：P4810 [COCI 2014/2015 #3] STOGOVI