AOJ 2170 Marked Ancestor[并查集][离线]

时间:2023-12-21 11:19:02

题意:

给你一颗N个节点的树,节点编号1到N。1总是节点的根。现在有两种操作:

  1. M v: 标记节点v
  2. Q v: 求出离v最近的标记的相邻节点。根节点一开始就标记好了。

现在给一系列操作,求出所有Q操作结果的和。

思路:

最坏情况下为整棵树成为一条链,单纯使用并查集(无压缩)查询复杂度最坏1e10。单纯使用并查集也能过。

正解应该是将查询存下来,存下每次Q操作的查询时间和查询结点,用qt和qv数组存储。另外设置mark数组存储这个结点被染色的最快时间。然后我们倒着进行查询操作,当当前查询的结点最早被染色时间小于当前时间时,就可以返回这个结点了,否则进行路径压缩(进入否则,说明这个结点的最快被染色时间大于查询时间,而我们是倒着进行操作的,说明后继的查询时间都比当前的查询时间小,不管怎么样,这个结点都不会被染色了,无用,直接拿来压缩掉)

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std; const int INF = 0x7f7f7f7f;
const int MAXN = 1e5 + 111; int p[MAXN];
int qt[MAXN], qv[MAXN], mark[MAXN];
int t; int find(int x) {
return mark[x] < t ? x : p[x] = find(p[x]); // 小于则说明在查询之前已经染过颜色
} int main()
{
int n, q;
while (~scanf("%d%d", &n, &q) && (n | q)) {
for (int i = 2; i <= n; ++i) {
scanf("%d", p + i);
mark[i] = INF;
} int cnt = 0, x;
char op[2];
for (int i = 1; i <= q; ++i) {
scanf("%s%d", op, &x);
if (op[0] == 'M') mark[x] = min(mark[x], i); // 记录最早染色时间
else {
qt[cnt] = i;
qv[cnt++] = x;
}
} ll ans = 0;
while (cnt --) {
t = qt[cnt]; // 查询发生的时间
ans += find(qv[cnt]);
}
printf("%lld\n", ans);
}
return 0;
}