洞穴勘探
2049: [Sdoi2008]Cave 洞穴勘测
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 11718 Solved: 5846
[Submit][Status][Discuss]
Description
辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。
Input
第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。
Output
对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）
本题的目的只是为了维护森林的联通性的变化。因而，本题用到的所有操作都是动态树的基本操作。
1）平衡树的翻转：这里指的是将平衡树中的所有节点逆序重排。
由于是splay进行维护，故给每个节点维护一个域isRev代表该结点及其子树是否翻转了。
要翻转一颗平衡树，只需令根节点的isRev改变状态，即原来为true现在变为false，反
之亦然。另外需要定义一个操作normalize，代表将平衡树某个子树"正常化"，实际上
某个子树“正常化”，实际上相当于线段树维护过程中的标记下传。注意，执行splay操
作之前（例如左旋和右旋），都要保证当前***作的结点已经执行过normalize了；
2）Path_Parent维护：由于Path_Parent是每个路径的属性，我们选择Path_Parent存放
在每个splay树的根节点中。因此，执行splay旋转操作时也需要维护该属性。注意，平衡
树中除了根节点之外，其余结点的Path_Parent指针都应为空。
例题是用了结构体的写法，
这玩意儿真的费力
//lcttree 操作简单link，cut，查询父节点是否在同一个splay中
但是检查起来真的雪崩
normalize步骤的右孩子打成了左孩子，tle了，样例都tm能过。。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=11000;
struct LinkCutTree{
private:
struct Node{
int idx;
bool isRev;
int father,lch,rch,path_parent;
};
Node nodes[maxn];
int nodeCnt,location[maxn];
inline void normalize(int p){//配合平衡树的翻转操作
if (nodes[p].isRev){
nodes[p].isRev=false;
nodes[nodes[p].lch].isRev=!nodes[nodes[p].lch].isRev;
nodes[nodes[p].rch].isRev=!nodes[nodes[p].rch].isRev;
swap(nodes[p].lch,nodes[p].rch);
}
}
void leftrotate(int x){
int y=nodes[x].father;
nodes[x].path_parent=nodes[y].path_parent;
nodes[y].path_parent=0;
nodes[y].rch=nodes[x].lch;
if (nodes[x].lch)
nodes[nodes[x].lch].father=y;
nodes[x].father=nodes[y].father;
if (nodes[y].father){
if (y==nodes[nodes[y].father].lch)
nodes[nodes[y].father].lch=x;
else nodes[nodes[y].father].rch=x;
}
nodes[y].father=x;
nodes[x].lch=y;
}
void rightrotate(int x){
int y=nodes[x].father;
nodes[x].path_parent=nodes[y].path_parent;
nodes[y].path_parent=0;//path_parent为维护一颗splay的path_parent的信息
nodes[y].lch=nodes[x].rch;
if (nodes[x].rch)
nodes[nodes[x].rch].father=y;
nodes[x].father=nodes[y].father;
if (nodes[y].father)
{
if (nodes[nodes[y].father].lch==y)
nodes[nodes[y].father].lch=x;
else nodes[nodes[y].father].rch=x;
}
nodes[y].father=x;
nodes[x].rch=y;
}
void splay(int x){
while (nodes[x].father)
{
int father=nodes[x].father;
normalize(nodes[x].father);
if (nodes[father].lch)
normalize(nodes[father].lch);
if (nodes[father].rch)
normalize(nodes[father].rch);
if (x==nodes[nodes[x].father].lch)
rightrotate(x);
else leftrotate(x);
}
}
//1)r如果节点v不是其所在实路径的头部，即v有子节点u与之用实边相连，那么需要
//断开这条边，方法是首先将节点v用splay操作旋转到所在平衡树的根节点，然后v肯定有
//右子树，故将v与v的右子树分离，同时将v的右子树的path_parent设置为v;
//2)如果节点v所在的平衡树包含根节点，那么该过程结束；否则，转步骤3）
//3)设u和v所在的平衡树的path_parent。将u用splay操作旋转到其所属平衡树的根节点，并且用v所在的平衡树替换u的右子树，这样就实现了实路径的向上延伸。
//当然到这里还没结束，我们需要分离原来u的右子树，u原来的右孩子记为w。此时w的path-parent就为u了，然后继续转步骤配（2）
void Access(int p){
splay(p);
normalize(p);
int q=nodes[p].rch;
nodes[p].rch=nodes[q].father=0;
nodes[q].path_parent=p;
for (q=nodes[p].path_parent;q;q=nodes[p].path_parent)
{
splay(q);
normalize(q);
int r=nodes[q].rch;
nodes[r].father=0;
nodes[r].path_parent=q;
nodes[q].rch=p;
nodes[p].father=q;
nodes[p].path_parent=0;
p=q;
}
splay(p);
}
int Find_Root(int p){
Access(p);
splay(p);
normalize(p);
while (nodes[p].lch)
p=nodes[p].lch;
splay(p);
return p;
}
void evert(int p){
Access(p);
splay(p);
nodes[p].isRev=!nodes[p].isRev;
normalize(p);
}
//该操作执行时，首先将u置为有根树的根节点，从而保证v一定是u的子节点。再对v执行access操作，我们便将u和v合并到同一颗平衡树中了。此时对v执行splay操作使其成为
//平衡树的根节点，同时分离v和v的左子树，便完成了删除操作。
void Cut(int p,int q){
evert(p);
Access(q);
splay(q);
normalize(q);
nodes[nodes[q].lch].father=0;
nodes[q].lch=0;
}
//我们首先将u变为其所在树的根节点，同时要将u用splay操作移动到其所在平衡树的根节点。此时，u的左子树必然为空。我们将v用splay操作移动到其所在平衡树的根节点，然后令
//u的左孩子为v，便完成了连接操作。
void Link(int p,int q){
evert(p);
splay(p);
normalize(p);
Access(q);
splay(q);
normalize(q);
nodes[p].lch=q;
nodes[q].father=p;
}
public:
void init()
{
nodeCnt=0;
memset(location,0,sizeof(location));
}
void Make_Tree(int idx){//建树这部分不是很清楚
int p=++nodeCnt;
location[idx]=p;
nodes[p].father=nodes[p].lch=nodes[p].rch=nodes[p].path_parent=0;
nodes[p].idx=idx;
}
int getRoot(int idx){
return nodes[Find_Root(idx)].idx;
}
void addEdge(int x,int y){
Link(location[x],location[y]);
}
void destroy(int x,int y){
Cut(location[x],location[y]);
}
};
LinkCutTree T;
int main()
{
int n,m;
scanf("%d %d",&n,&m);
T.init();
for (int i=1;i<=n;i++)
T.Make_Tree(i);
while (m--){
int u,v;
char cmd[10];
scanf("%s %d %d",cmd,&u,&v);
if (cmd[0]=='C')
T.addEdge(u,v);
else if (cmd[0]=='D')
T.destroy(u,v);
else {
int x=T.getRoot(u),y=T.getRoot(v);
if (x==y)
printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
京公网安备 11010502036488号