2049: [Sdoi2008]Cave 洞穴勘测
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 7911 Solved: 3700[][][]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”。（不含双引号）
Sample Input
Sample Output
HINT
10%的数据满足n≤1000, m≤20000
20%的数据满足n≤2000, m≤40000
30%的数据满足n≤3000, m≤60000
40%的数据满足n≤4000, m≤80000
50%的数据满足n≤5000, m≤100000
60%的数据满足n≤6000, m≤120000
70%的数据满足n≤7000, m≤140000
80%的数据满足n≤8000, m≤160000
90%的数据满足n≤9000, m≤180000
100%的数据满足n≤10000, m≤200000
保证所有Destroy指令将摧毁的是一条存在的通道本题输入、输出规模比较大，建议c\c++选手使用scanf和printf进行I\O操作以免超时
Source
Link-Cut-Tree模板题，OTZ LincHpin
从WC回来受了刺激，决定好好学LCT。
1 #include2 3 template 4 inline void swap(T &a, T &b) 5 { 6 T c; 7 8 c = a; 9 a = b; 10 b = c; 11 } 12 13 const int mxn = 10005; 14 15 int n, m; 16 17 struct node 18 { 19 node *son[2]; 20 node *father; 21 bool reverse; 22 23 inline node(void) 24 { 25 son[0] = NULL; 26 son[1] = NULL; 27 father = NULL; 28 reverse = false; 29 } 30 31 inline bool isRoot(void) 32 { 33 if (father == NULL) 34 return true; 35 36 if (this == father->son[0]) 37 return false; 38 if (this == father->son[1]) 39 return false; 40 41 return true; 42 } 43 44 inline void pushDown(void) 45 { 46 if (reverse) 47 { 48 reverse = false; 49 50 swap(son[0], son[1]); 51 52 if (son[0])son[0]->reverse ^= true; 53 if (son[1])son[1]->reverse ^= true; 54 } 55 } 56 }tree[mxn]; 57 58 inline void connect(node *f, node *t, bool k) 59 { 60 if (t != NULL) 61 t->father = f; 62 if (f != NULL) 63 f->son[k] = t; 64 } 65 66 inline void rotate(node *t) 67 { 68 node *f = t->father; 69 node *g = f->father; 70 71 bool s = f && f->son[1] == t; 72 73 connect(f, t->son[!s], s); 74 connect(t, f, !s); 75 76 t->father = g; 77 if (g && g->son[0] == f) 78 g->son[0] = t; 79 if (g && g->son[1] == f) 80 g->son[1] = t; 81 } 82 83 inline void push(node *t) 84 { 85 static node *stk[mxn]; 86 87 int top = 0; 88 89 stk[top++] = t; 90 91 while (!t->isRoot()) 92 stk[top++] = t = t->father; 93 94 while (top)stk[--top]->pushDown(); 95 } 96 97 inline void splay(node *t) 98 { 99 push(t);100 101 while (!t->isRoot())102 {103 node *f = t->father;104 node *g = f->father;105 106 if (f->isRoot())107 rotate(t);108 else109 {110 bool a = f && f->son[1] == t;111 bool b = g && g->son[1] == f;112 113 if (a == b)114 rotate(f), rotate(t);115 else116 rotate(t), rotate(t);117 }118 }119 }120 121 inline void access(node *t)122 {123 node *p = NULL;124 125 while (t != NULL)126 {127 splay(t);128 t->son[1] = p;129 p = t, t = t->father;130 }131 }132 133 inline void makeRoot(node *t)134 {135 access(t), splay(t), t->reverse ^= true;136 }137 138 inline void link(node *t, node *f)139 {140 makeRoot(t), t->father = f;141 }142 143 inline void cut(node *t)144 {145 splay(t);146 147 if (t->son[0])148 t->son[0]->father = NULL;149 if (t->son[1])150 t->son[1]->father = NULL;151 152 t->son[0] = t->son[1] = NULL;153 }154 155 inline node *find(node *t)156 {157 access(t), splay(t);158 159 node *r = t;160 161 while (r->son[0])162 r = r->son[0];163 164 return r;165 }166 167 signed main(void)168 {169 scanf("%d%d", &n, &m);170 171 while (m--)172 {173 static int x, y;174 static char s[50];175 176 scanf("%s%d%d", s, &x, &y);177 178 if (s[0] == 'C')179 link(tree + x, tree + y);180 else if (s[0] == 'D')181 makeRoot(tree + y), access(tree + x), cut(tree + x);182 else183 puts(find(tree + x) == find(tree + y) ? "Yes" : "No");184 }185 }
@AUthor: YouSiki