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
解题思路：
蒟蒻写的第一道LCT题，大概就是模板吧。
1 #include2 #include 3 #include 4 #define lll tr[spc].ch[0] 5 #define rrr tr[spc].ch[1] 6 #define ls ch[0] 7 #define rs ch[1] 8 const int S=200000; 9 struct trnt{ 10 int ch[2]; 11 int lzt; 12 int fa; 13 bool anc; 14 }tr[S]; 15 int n,m; 16 char cmd[10]; 17 namespace Splay{ 18 void trr(int spc) 19 { 20 if(!spc) 21 return ; 22 std::swap(lll,rrr); 23 tr[spc].lzt^=1; 24 return ; 25 } 26 void pushdown(int spc) 27 { 28 if(tr[spc].lzt) 29 { 30 trr(lll); 31 trr(rrr); 32 tr[spc].lzt=0; 33 } 34 return ; 35 } 36 bool whc(int spc) 37 { 38 return tr[tr[spc].fa].rs==spc; 39 } 40 void recal(int spc) 41 { 42 if(!tr[spc].anc) 43 recal(tr[spc].fa); 44 pushdown(spc); 45 } 46 void rotate(int spc) 47 { 48 int f=tr[spc].fa; 49 bool k=whc(spc); 50 tr[f].ch[k]=tr[spc].ch[!k]; 51 tr[spc].ch[!k]=f; 52 if(tr[f].anc) 53 { 54 tr[f].anc=0; 55 tr[spc].anc=1; 56 }else 57 tr[tr[f].fa].ch[whc(f)]=spc; 58 tr[spc].fa=tr[f].fa; 59 tr[f].fa=spc; 60 tr[tr[f].ch[k]].fa=f; 61 } 62 void splay(int spc) 63 { 64 recal(spc); 65 while(!tr[spc].anc) 66 { 67 int ft=tr[spc].fa; 68 if(tr[ft].anc) 69 { 70 rotate(spc); 71 return ; 72 } 73 if(whc(spc)^whc(ft)) 74 rotate(spc); 75 else 76 rotate(ft); 77 rotate(spc); 78 } 79 return ; 80 } 81 } 82 using namespace Splay; 83 namespace LCT{ 84 void Access(int spc) 85 { 86 int lsts=0; 87 while(spc) 88 { 89 splay(spc); 90 tr[lsts].anc=0; 91 tr[rrr].anc=1; 92 rrr=lsts; 93 lsts=spc; 94 spc=tr[spc].fa; 95 } 96 return ; 97 } 98 void Move_to_root(int spc) 99 {100 Access(spc);101 splay(spc);102 trr(spc);103 }104 void Link(int a,int b)105 {106 Move_to_root(a);107 tr[a].fa=b;108 return ;109 }110 void Cut(int a,int b)111 {112 Move_to_root(a);113 Access(b);114 splay(a);115 tr[a].rs=0;116 tr[b].fa=0;117 tr[b].anc=true;118 return ;119 }120 bool Check(int a,int b)121 {122 Move_to_root(a);123 Access(b);124 splay(a);125 while(!tr[b].anc)126 b=tr[b].fa;127 return (bool)(b==a);128 }129 }130 using namespace LCT;131 void Print(bool x)132 {133 puts(x?"Yes":"No");134 return ;135 }136 int main()137 {138 scanf("%d%d",&n,&m);139 for(int i=1;i<=n;i++)140 tr[i].anc=true;141 while(m--)142 {143 int x,y;144 scanf("%s",cmd);145 scanf("%d%d",&x,&y);146 if(cmd[0]=='C')147 Link(x,y);148 if(cmd[0]=='D')149 Cut(x,y);150 if(cmd[0]=='Q')151 Print(Check(x,y));152 }153 return 0;154 }