求教树的dfs序问题

例如这样，1号是建树时的根，4号是实际的根，现在把2的父亲由3换成5，怎么搞？
1和2、3和4、4和5之间有很多节点，不能直接反过来。

我想了一个比较囧的方法…… 不知道行不行…… DFS序时候进栈放入序列，出栈也放入序列。 这样每个结点在序列中出现两次，子树对应其根出现在序列中的两个位置为端点的区间。
这样的好处就是不用额外维护子树对应区间了…… 然后问题就简单了……
先把要砍的子树提取出来……（要么是连续一段，要么是整个序列扣掉一段）
然后插入到要拼的位置……
像3楼那种情况的话，新的dfs序子树根会变成3…… 不过无所谓，不影响查询……
具体操作的话，可以考虑用一个数组记录下来每个结点在dfs序中对应的两个splay结点…… 然后提取子树就可以直接用那两个splay结点砍出来…… 树砍出来后，查询和判断某个结点是否在子树内也可以做了……
这东西我没实现过（一般见到换根砍树就不想做了>_<）…… 只是刚才随便想的…… 很可能有错，欢迎拍砖……