作者：_我的最愛 | 来源：互联网 | 2024-11-18 20:11
题目编号：2049[SDOI2008]CaveExploration。题目描述了一种动态图操作场景，涉及三种基本操作：断开两个节点间的连接（destroy(a,b)）、建立两个节点间的连接（connect(a,b)）以及查询两节点是否连通（query(a,b)）。所有操作均确保图中无环存在。
SDOI2008 Cave Exploration - 动态树结构应用
题目描述了一个动态图问题，其中需要支持三种操作：destroy(a,b)用于移除节点a和b之间的直接连接；connect(a,b)用于创建节点a和b之间的直接连接；query(a,b)用于检查节点a和b是否通过一系列直接或间接的连接相互可达。在整个过程中，保证所有操作都不会导致图中出现环路，因此该图始终保持为森林结构。
解题策略：此题可通过Link-Cut Tree（LCT）来高效解决。LCT是一种能够高效处理动态树问题的数据结构，特别适用于本题中的动态连通性查询与修改。难点在于如何正确实现destroy操作，即如何安全地断开两个节点间的连接而不破坏LCT的性质。解决方案是先使用change_root操作将其中一个节点变为树的根，随后通过access操作确保这两个节点不在同一路径上，最后执行splay操作，并将目标节点的父指针设置为0，从而完成断开操作。
以下是使用C++实现的代码示例：
#include
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 7;
int ch[MAXN][2], fa[MAXN], rev[MAXN];
void pushup(int x) {
// 更新节点x的信息
}
void pushdown(int x) {
if (rev[x]) {
swap(ch[x][0], ch[x][1]);
rev[ch[x][0]] ^= 1;
rev[ch[x][1]] ^= 1;
rev[x] = 0;
}
}
bool nroot(int x) {
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
void rotate(int x) {
int y = fa[x], z = fa[y], which = ch[y][1] == x;
ch[y][which] = ch[x][!which];
fa[ch[x][!which]] = y;
ch[x][!which] = y;
fa[y] = x;
fa[x] = z;
if (nroot(y)) ch[z][ch[z][1] == y] = x;
pushup(y);
}
void splay(int x) {
static int st[MAXN];
int top = 0;
st[++top] = x;
for (int i = x; nroot(i); i = fa[i]) st[++top] = fa[i];
while (top) pushdown(st[top--]);
for (; nroot(x); rotate(x))
if (nroot(fa[x]))
rotate((ch[fa[fa[x]]][1] == fa[x]) == (ch[fa[x]][1] == x) ? fa[x] : x);
pushup(x);
}
void access(int x) {
for (int t = 0; x; t = x, x = fa[x]) {
splay(x);
ch[x][1] = t;
pushup(x);
}
}
void makeroot(int x) {
access(x);
splay(x);
rev[x] ^= 1;
}
int findroot(int x) {
access(x);
splay(x);
while (ch[x][0]) x = ch[x][0];
splay(x);
return x;
}
bool link(int x, int y) {
if (findroot(x) != findroot(y)) {
makeroot(x);
fa[x] = y;
return true;
}
return false;
}
bool cut(int x, int y) {
if (findroot(x) == findroot(y) && x != y) {
makeroot(x);
access(y);
splay(y);
if (ch[y][0] == x && !ch[x][1]) {
ch[y][0] = fa[x] = 0;
return true;
}
}
return false;
}
bool query(int x, int y) {
return findroot(x) == findroot(y);
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
ch[i][0] = ch[i][1] = fa[i] = 0;
rev[i] = 0;
}
string op;
while (m--) {
cin >> op;
int u, v;
cin >> u >> v;
if (op[0] == 'Q') cout <<(query(u, v) ? "Yes" : "No") <
京公网安备 11010802041100号