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;
}