题意：一开始给定n个盒子的摆的嵌套关系。有两种操作，1.MOVE x y：把编号x的箱子及其包含的箱子放进编号为y的箱子；
2.QUERY x :查询编号x的箱子所在的最靠外的箱子。
方法一：splay+括号序
思路：将全部的树逐个dfs，这样对于每一棵树都可以得到一个括号序列，对于MOVE操作，我们将那个根所在的左右括号的一整段
取出，连接到新的结点的左括号右边，这么做我们可以保证得到的一定也是一个括号序列。我们将x和x+n分别旋根，这样我们可以得到一个x和x+n，x+n是根，x是其左子树的某一个结点，这样x的左子树和x+n的右子树是无效的，我们剪掉它们，并且将x+n的右子树接到x的左子树最后，接着把x+n旋根，保证平衡性。对于QUERY操作，我们直接去找其结点所在的括号序列靠最左边的是谁就可以了。详见代码：
/*********************************************************
file name: hdu2475.cpp
author : kereo
create time: 2015年02月18日 星期三 14时29分43秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=100+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x->ch[0])
#define R(x) (x->ch[1])
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,m,edge_cnt,cnt;
char str[N];
int head[MAXN],seq[MAXN],vis[MAXN];
struct Edge{
int v,next;
}edge[MAXN];
struct node{
node *fa,*ch[2];
}nod[MAXN],*root,*null;
struct Splay{
void rotate(node *x,int d){
node *y=x->fa;
//push_down(y); push_down(x);
y->ch[d^1]=x->ch[d];
if(x->ch[d]!=null)
x->ch[d]->fa=y;
x->fa=y->fa;
if(y->fa!=null){
int d=y->fa->ch[0] == y ? 0 : 1;
y->fa->ch[d]=x;
}
y->fa=x; x->ch[d]=y;
//push_up(y);
}
void splay(node *x,node *fa){
while(x->fa!=fa){
//push_down(x);
node *y=x->fa;
if(y->fa == fa){
int d=y->ch[0] == x ? 1 : 0;
rotate(x,d);
}
else{
int d=y->fa->ch[0] == y ? 1 : 0;
if(y->ch[d] == x){
rotate(x,d^1); rotate(x,d);
}
else{
rotate(y,d); rotate(x,d);
}
}
}
//push_up(x);
if(fa == null)
root=x;
}
void newnode(node *&x,node *fa,int pos){
x=&nod[pos];
x->fa=fa; L(x)=R(x)=null;
}
void build(node *&rt,node *fa,int l,int r){
if(l>r)
return ;
int mid=(l+r)>>1;
newnode(rt,fa,seq[mid]);
build(L(rt),rt,l,mid-1); build(R(rt),rt,mid+1,r);
//push_up(rt);
}
void init(){
null=&nod[0]; root=null;
L(null)=R(null)=null->fa=null;
}
void MOVE(int x,int y){
if(x == y)
return ;
splay(&nod[x],null);
splay(&nod[x+n],&nod[x]);
node *tmp;
for(tmp=&nod[y];tmp!=null;tmp=tmp->fa){
if((&nod[x+n])->ch[0] == tmp)
return ;
}
node *pre=(&nod[x])->ch[0],*suf=(&nod[x+n])->ch[1];
(&nod[x])->ch[0]=(&nod[x+n])->ch[1]=pre->fa=suf->fa=null;
if(pre!=null && suf!=null){
while(L(suf)!=null)
suf=L(suf);
pre->fa=suf; L(suf)=pre;
}
if(y == 0)
return ;
splay(&nod[y],null);
for(tmp=(&nod[y])->ch[1];L(tmp)!=null;tmp=L(tmp)) ;
splay(tmp,&nod[y]);
L(tmp)=&nod[x]; (&nod[x])->fa=tmp;
}
int QUERY(int x){
node *tmp=&nod[x];
splay(tmp,null);
for(;L(tmp)!=null;tmp=L(tmp)) ;
return tmp-nod;
}
}spt;
void init(){
edge_cnt=0;
memset(vis,0,sizeof(vis));
memset(head,-1,sizeof(head));
}
void addedge(int u,int v){
edge[edge_cnt].v=v;
edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;
}
void dfs(int u){
seq[++cnt]=u;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
dfs(v);
}
seq[++cnt]=u+n;
}
int main(){
int flag=1;
//freopen("in.txt","r",stdin);
while(~scanf("%d",&n)){
init();
spt.init();
if(flag)
flag=0;
else
printf("\n");
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
if(x == 0)
vis[i]=1;
else
addedge(x,i);
}
for(int i=1;i<=n;i++){
if(!vis[i])
continue;
cnt=0;
dfs(i);
spt.build(root,null,1,cnt);
}
scanf("%d",&m);
while(m--){
scanf("%s",str);
if(strcmp(str,"MOVE") == 0){
int x,y;
scanf("%d%d",&x,&y);
spt.MOVE(x,y);
}
else if(strcmp(str,"QUERY") == 0){
int x;
scanf("%d",&x);
int ans=spt.QUERY(x);
printf("%d\n",ans);
}
}
}
return 0;
}
方法二：Link-Cut Tree
思路：参阅《QTREE的一些研究》。tip:注释掉的部分导致TLE的原因：y=x->fa,恰好根是y->fa，且x,y,y->fa为“一字型”,那么会先把根
转下去，那么更新x->par的时候就会出现问题。详见代码：
/*********************************************************
file name: hdu2475.cpp
author : kereo
create time: 2015年02月21日 星期六 10时23分07秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=100+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x->ch[0])
#define R(x) (x->ch[1])
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,m;
char str[N];
struct node{
node *ch[2],*par,*fa;
}nod[MAXN],*null,*root;
struct LCT{
void rotate(node *x,int d){
node *y=x->fa;
//push_down(y); push_down(x);
y->ch[d^1]=x->ch[d];
x->ch[d]->fa=y;
x->fa=y->fa;
if(y->fa!=null){
int d=y->fa->ch[0] == y ? 0 : 1;
y->fa->ch[d]=x;
}
y->fa=x; x->ch[d]=y;
//push_up(y);
}
/*void splay(node *x,node *fa){
while(x->fa!=fa){
node *y=x->fa;
if(y->fa == fa){
x->par=y->par; y->par=null;
int d=y->ch[0] == x ? 1 : 0;
rotate(x,d);
}
else{
int d=y->fa->ch[0] == y ? 1 : 0;
if(y->ch[d] == x){
rotate(x,d^1); rotate(x,d);
}
else{
rotate(y,d); rotate(x,d);
}
}
}
if(fa == null)
root=x;
}*/
node* findroot(node *x){
while(x->fa!=null)
x=x->fa;
return x;
}
void splay(node *x,node *fa){
node *tmp=findroot(x);
if(x == tmp)
return ;
x->par=tmp->par; tmp->par=null;
while(x->fa!=fa){
node *y=x->fa;
if(y->fa == fa){
int d=y->ch[0] == x ? 1 : 0;
rotate(x,d);
}
else{
int d=y->fa->ch[0] == y ? 1 : 0;
if(y->ch[d] == x){
rotate(x,d^1); rotate(x,d);
}
else{
rotate(y,d); rotate(x,d);
}
}
}
}
void Access(node *x){
node *tmp=null;
while(x!=null){
splay(x,null);
if(R(x)!=null){
R(x)->fa=null; R(x)->par=x;
}
R(x)=tmp;
if(tmp!=null){
tmp->fa=x; tmp->par=null;
}
tmp=x; x=x->par;
}
}
void Cut(node *x){
Access(x); splay(x,null);
if(L(x)!=null){
L(x)->par=x->par; x->par=null;
L(x)->fa=null; L(x)=null;
}
}
void Link(node *x,node *y){
if(y == null)
Cut(x);
else{
Access(y); splay(y,null);
node *tmp=findroot(x);
if(tmp == y)
return ;
Cut(x); x->par=y;
Access(x);
}
}
void init(){
null=&nod[0]; root=null;
L(root)=R(root)=root->fa=null;
}
void newnode(node *&x,node *fa,node *par,int pos){
x=&nod[pos];
x->fa=fa; x->par=par; L(x)=R(x)=null;
}
int query(node *x){
Access(x); splay(x,null);
while(L(x)!=null)
x=L(x);
return x-nod;
}
}lct;
int main(){
int flag=1;
//freopen("in.txt","r",stdin);
while(~scanf("%d",&n)){
if(flag)
flag=0;
else
printf("\n");
lct.init();
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
lct.newnode(root,null,&nod[x],i);
}
//for(int i=1;i<=n;i++)
// printf("i=%d par=%d fa=%d\n",i,(&nod[i])->par-nod,(&nod[i])->fa-nod);
scanf("%d",&m);
while(m--){
scanf("%s",str);
if(strcmp(str,"MOVE") == 0){
int x,y;
scanf("%d%d",&x,&y);
lct.Link(&nod[x],&nod[y]);
}
else if(strcmp(str,"QUERY") == 0){
int x;
scanf("%d",&x);
int ans=lct.query(&nod[x]);
printf("%d\n",ans);
}
}
}
return 0;
}