LCA LinkCutTree
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C&lang=jp
参考スライド
http://www.slideshare.net/iwiwi/2-12188845
Link Cut TreeでLCAをやってみました。
Link Cut Tree部分はほとんど参考スライドのものと同じです。
#include<iostream> #include<vector> #include<algorithm> #include<queue> #define INF (1<<29) #define max_n 10000 using namespace std; struct node_t{ node_t *pp,*lp,*rp; int id,val,mini,minId,lazy; node_t(int id,int v):id(id),val(v){ pp=lp=rp=NULL; lazy=0; } bool is_root(){ return !pp || (pp->lp != this && pp->rp != this); } void rotr(){ node_t *q=pp,*r=q->pp; if((q->lp=rp))rp->pp=q; rp=q;q->pp=this; if((pp=r)){ if(r->lp==q)r->lp=this; if(r->rp==q)r->rp=this; } } void rotl(){ node_t *q=pp,*r=q->pp; if((q->rp=lp))lp->pp=q; lp=q;q->pp=this; if((pp=r)){ if(r->lp==q)r->lp=this; if(r->rp==q)r->rp=this; } } void splay(){ while(!is_root()){ node_t *q=pp; if(q->is_root()){ if(q->lp==this)rotr(); else rotl(); } else { node_t *r=q->pp; if(r->lp==q){ if(q->lp==this){q->rotr();rotr();} else {rotl();rotr();} } else { if(q->rp==this){q->rotl();rotl();} else {rotr();rotl();} } } } } }; node_t *expose(node_t *x){ node_t *rp=NULL; for(node_t *p=x;p;p=p->pp){ p->splay(); p->rp=rp; rp=p; } x->splay(); return rp; } node_t *find_root(node_t *x){ expose(x); while(x->lp)x=x->lp; return x; } void link(node_t *c,node_t *p){ expose(c); expose(p); c->pp=p; p->rp=c; } node_t *lowestCommonAncestor(node_t *x,node_t* y){ expose(x); return expose(y); } node_t *node[100001]; int main(void){ int n; cin >> n; for(int i=0;i<n;i++)node[i]=new node_t(i,0); for(int i=0;i<n;i++){ int k,t; cin >> k; for(int j=0;j<k;j++){ cin >> t; link(node[t],node[i]); } } int q; cin >> q; for(int i=0;i<q;i++){ int u,v; cin >> u >> v; cout << lowestCommonAncestor(node[u],node[v])->id << endl; } return 0; }