1、题目大意:就是一个动态维护森林联通性的题
2、分析:lct模板题
#include <stack> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; #define LL long long #define eps 1e-7 int n, m; namespace LinkCutTree{ struct Node{ Node *ch[2], *fa; bool rev; Node(){ ch[0] = ch[1] = NULL; fa = NULL; rev = false; } inline int which(){ if(fa == NULL || (fa -> ch[0] != this && fa -> ch[1] != this)) return -1; return fa -> ch[1] == this; } inline bool reverse(){ if(this) rev ^= 1; } inline void pd(){ if(rev){ swap(ch[0], ch[1]); if(ch[0] != NULL) ch[0] -> reverse(); if(ch[1] != NULL) ch[1] -> reverse(); rev = false; } } } ft[10010], *pos[10010]; inline void rotate(Node *o){ Node *p = o -> fa; int l = o -> which(), r = l ^ 1; o -> fa = p -> fa; if(p -> which() != -1) p -> fa -> ch[p -> which()] = o; p -> ch[l] = o -> ch[r]; if(o -> ch[r]) o -> ch[r] -> fa = p; o -> ch[r] = p; p -> fa = o; } inline void splay(Node* o){ static stack<Node*> st; if(!o) return; Node* p = o; while(1){ st.push(p); if(p -> which() == -1) break; p = p -> fa; } while(!st.empty()){ st.top() -> pd(); st.pop(); } while(o -> which() != -1){ p = o -> fa; if(p -> which() != -1){ if(p -> which() ^ o -> which()) rotate(o); else rotate(p); } rotate(o); } } inline void Access(Node* o){ Node* p = NULL; while(o != NULL){ splay(o); o -> ch[1] = p; p = o; o = o -> fa; } } inline void MovetoRoot(Node* o){ Access(o); splay(o); o -> reverse(); } inline Node* FindRoot(Node* o){ while(o -> fa != NULL){ o = o -> fa; } return o; } inline void Link(Node* x, Node* y){ MovetoRoot(x); x -> fa = y; } inline void Cut(Node* x, Node* y){ MovetoRoot(x); Access(y); splay(y); x -> fa = NULL; y -> ch[0] = NULL; } inline void init(){ for(int i = 1; i <= n; i ++) pos[i] = &ft[i]; } inline void Connect(int u, int v){ Link(pos[u], pos[v]); } inline void Destroy(int u, int v){ Cut(pos[u], pos[v]); } inline bool Query(int u, int v){ return FindRoot(pos[u]) == FindRoot(pos[v]); } } int main(){ char op[10]; int u, v; scanf("%d%d", &n, &m); LinkCutTree::init(); for(int i = 1; i <= m; i ++){ scanf("%s", op); scanf("%d%d", &u, &v); if(op[0] == 'C') LinkCutTree::Connect(u, v); else if(op[0] == 'D') LinkCutTree::Destroy(u, v); else puts(LinkCutTree::Query(u, v) ? "Yes" : "No"); } return 0; }