树型转线型。第一次听说这个概念. . . , 可是曾经已经接触过了，如LCA的预处理部分和树链剖分等。可是没想到还能这么用，三者虽说有不同可是大体思想还是非常相近的，学习了。
推荐博客http://blog.csdn.net/lyhypacm/article/details/6734748
转成线型之后。就变成了伸展树的模板题。
另外要注意，伸展树的特点是平均时间复杂度接近log(n)。所以一定要记得每次操作之后都要伸展。再次学习了。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map> #pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 9999991
#define lowbit(x) (x&(-x)) using namespace std; const int MAXN = 50010; struct N
{
//info
int son[2],pre,ls,rs,s; //data
int id;
} st[MAXN*2]; int Top; void Updata(int root)
{
st[root].ls = (st[root].son[0] == -1 ? 0 : st[st[root].son[0]].s);
st[root].rs = (st[root].son[1] == -1 ? 0 : st[st[root].son[1]].s);
st[root].s = st[root].ls + st[root].rs + 1;
} void Push_Down(int root)
{
;
} void Rotate(int root,int dir)
{
st[st[root].pre].son[dir] = st[root].son[1^dir];
st[root].son[1^dir] = st[root].pre; if(st[st[st[root].pre].pre].son[0] == st[root].pre)
st[st[st[root].pre].pre].son[0] = root;
else
st[st[st[root].pre].pre].son[1] = root;
int temp = st[root].pre;
st[root].pre = st[st[root].pre].pre;
st[temp].pre = root; if(st[temp].son[dir] != -1)
st[st[temp].son[dir]].pre = temp;
Updata(temp);
Updata(root);
} int Splay(int root,int goal)
{
while(st[root].pre != goal)
{
Rotate(root,(st[st[root].pre].son[0] == root ? 0 : 1));
} return root;
} int Search_Site(int root,int site)
{
Push_Down(root); int temp; if(st[root].ls + 1 == site)
temp = root;
else if(st[root].ls + 1 < site)
temp = Search_Site(st[root].son[1],site-st[root].ls-1);
else
temp = Search_Site(st[root].son[0],site); Updata(root);
return temp;
} struct E
{
int v,next;
} edge[MAXN]; int head[MAXN]; int degree[MAXN]; int Top_E; void Link(int u,int v)
{
edge[Top_E].v = v;
edge[Top_E].next = head[u];
head[u] = Top_E++;
} int vis[MAXN*2]; int Top_S; int L[MAXN],R[MAXN]; void dfs(int root)
{
vis[Top_S++] = root; for(int p = head[root]; p != -1; p = edge[p].next)
{
dfs(edge[p].v);
} vis[Top_S++] = -root;
} void NewNode(int root,int id,int pre)
{
st[root].son[0] = -1,st[root].son[1] = -1;
st[root].pre = pre; st[root].id = id;
} void Init(int &root,int l,int r,int pre)
{
if(l > r)
return ; int mid = (l+r)>>1; root = Top++; NewNode(root,vis[mid],pre); if(vis[mid] > 0)
L[vis[mid]] = root;
else
R[-vis[mid]] = root;
Init(st[root].son[0],l,mid-1,root);
Init(st[root].son[1],mid+1,r,root); Updata(root);
} int Query(int v)
{
Splay(L[v],0);
return st[Search_Site(L[v],1)].id;
} void Move(int u,int v)
{
if(u == v)
return ;
int site = R[v]; Splay(R[u],0);
Splay(L[u],0); while(site)
{
if(st[site].pre == R[u] && st[R[u]].son[0] == site)
return ;
site = st[site].pre;
} if(st[L[u]].son[0] != -1)
{
int lt = st[L[u]].son[0];
int rt = st[R[u]].son[1]; st[L[u]].son[0] = -1;
st[R[u]].son[1] = -1; Updata(R[u]);
Updata(L[u]); st[lt].pre = 0; int root = Splay(Search_Site(lt,st[lt].s),0);
st[root].son[1] = rt;
st[rt].pre = root;
Updata(root);
} if(v)
{
Splay(L[v],0);
Splay(Search_Site(L[v],st[L[v]].ls+2),L[v]);
st[st[L[v]].son[1]].son[0] = L[u];
st[L[u]].pre = st[L[v]].son[1];
Updata(st[L[v]].son[1]);
Updata(L[v]);
}
} int main()
{
int n,m; int i,j,u,v; int root; bool blank = false; while(scanf("%d",&n) != EOF)
{
if(blank)
printf("\n");
else
blank = true;
Top_E = 0;
memset(head,-1,sizeof(int)*(n+2));
memset(degree,0,sizeof(int)*(n+2)); for(i = 1; i <= n; ++i)
{
scanf("%d",&u);
if(u)
{
Link(u,i);
degree[i]++;
}
} st[0].son[0] = -1,st[1].son[1] = -1; Top = 1; for(i = 1; i <= n; ++i)
{
if(degree[i] == 0)
{ Top_S = 1;
dfs(i); root = -1;
Init(root,1,Top_S-1,0);
}
} scanf("%d",&m);
L[0] = R[0] = 0;
char s[10];
while(m--)
{
scanf("%s",s);
if(s[0] == 'Q')
{
scanf("%d",&u);
printf("%d\n",Query(u)); }
else
{
scanf("%d %d",&u,&v);
Move(u,v);
}
}
}
return 0;
}