AOJ 2170 并查集

题目链接:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2170

有一棵树,初始时只有根节点被染了色。现在有一系列操作,可以分为两类:

  1. 给结点 $p$ 染色
  2. 求结点 $p$ 最近的且被染色的祖先

思路

不难想到并查集中的 getfa 函数,不过按照题目要求顺序处理肯定会 TLE。

不过我们可以发现,随着时间的推移,越来越多的结点被染色,某个结点的最近的且被染色的祖先只会越来越近。因此我们可以逆向思考,记录下所有的操作,从最终状态往前处理。

本题的关键就是 getfa 函数,注意路径压缩只能在逆向时使用

2170.cppview raw
#include <iostream>
#include <stdio.h>
#include <cstring>
#define ll long long
#define maxn 100005
using namespace std;

pair<char, int> query[maxn];
int par[maxn], flag[maxn], n, q;

int getfa(int x) {
if (flag[x])
return x;
else {
par[x] = getfa(par[x]);
return par[x];
}
}

int main() {
while (scanf("%d %d", &n, &q) == 2 && n && q) {
memset(flag, 0, sizeof flag);
flag[0] = 1; par[0] = 0;
for (int i = 1; i < n; i++) {
int p; scanf("%d", &p);
par[i] = p - 1;
}
for (int i = 0; i < q; i++) {
scanf(" %c %d", &query[i].first, &query[i].second);
query[i].second--;
if (query[i].first == 'M')
flag[query[i].second]++;
}
ll ans = 0;
for (int i = q - 1; ~i; i--)
if (query[i].first == 'M')
flag[query[i].second]--;
else
ans += getfa(query[i].second) + 1;
printf("%lld\n", ans);
}
return 0;
}