【背景】
2012年1月19日，本沙茶开始看动态树论文，搞懂了一些；
2012年1月20日，开始写动态树，使用的题是QTREE，花了整整一天时间总算写完，交上去，TLE……
2012年1月21日，又调了一天，对拍了100+组随机数据都瞬间出解，交上去，还是TLE……
2012年2月8日，WC2012，fanhq666讲动态树，又搞懂了一点，于是当天晚上回房间以后就开始继续调，交上去，TLE……
2012年2月9日，晚上继续调QTREE，TLE……
在挑战动态树N次失败之后，本沙茶昨天再次去挑战动态树……这次换了一个题：
BZOJ2002（传说中的动态树模板题）
一开始还是TLE了，不过后来把数据搞到手以后，发现TLE的原因并不是常数大，而是死循环了，最后，经过2h+的调试，总算找到了错误（有好几处），终于AC了……
【关于BZOJ2002】
从每个点i往(i+Ki)连一条边，如果(i+Ki)不存在则往一个附加的结点（本沙茶的代码中为1号点，因为0号点是不能使用的）连一条边，这样就是一棵树（除1号点外，每个点有且只有一个后继……），然后，问题中的两种操作就是“改接”和“询问到根的距离”，可以用动态树搞；
【代码】
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 200004, INF = ~0U >> 2;
struct node {
int c[2], p, sz;
bool rf, d;
} T[MAXN];
int n;
void sc(int _p, int _c, bool _d)
{
T[_p].c[_d] = _c; T[_c].p = _p; T[_c].d = _d;
}
void upd(int No)
{
T[No].sz = T[T[No].c[0]].sz + T[T[No].c[1]].sz + 1;
}
void rot(int No)
{
int p = T[No].p; bool d = T[No].d;
if (T[p].rf) {T[p].rf = 0; T[No].rf = 1; T[No].p = T[p].p;} else sc(T[p].p, No, T[p].d);
sc(p, T[No].c[!d], d); sc(No, p, !d); upd(p);
}
void splay(int No)
{
int p; while (!T[No].rf) if (T[p = T[No].p].rf) rot(No); else if (T[No].d == T[p].d) {rot(p); rot(No);} else {rot(No); rot(No);} upd(No);
}
int access(int x)
{
int tmp = 0;
do {
splay(x); T[T[x].c[1]].rf = 1; T[tmp].rf = 0; sc(x, tmp, 1); upd(x); tmp = x; x = T[x].p;
} while (x);
}
void cut(int x)
{
access(x); splay(x); T[T[x].c[0]].rf = 1; T[T[x].c[0]].p = 0; sc(x, 0, 0); upd(x);
}
void join(int x, int p)
{
access(x); T[x].p = p;
}
int main()
{
int m, x, y, z;
scanf("%d", &n); n++;
re3(i, 2, n) {scanf("%d", &x); T[i].sz = 1; T[i].rf = 1; if (i + x <= n) T[i].p = i + x; else T[i].p = 1;}
T[1].sz = 1; T[1].rf = 1; T[0].sz = 0;
scanf("%d", &m);
re(i, m) {
scanf("%d", &x);
if (x == 1) {
scanf("%d", &y); y += 2;
access(y); splay(y); printf("%d\n", T[T[y].c[0]].sz);
} else {
scanf("%d%d", &y, &z); y += 2;
cut(y); if (y + z <= n) join(y, y + z); else join(y, 1);
}
}
return 0;
}
【易疵点】
（1）注意一个点的父结点p有两种可能：如果该结点是某棵伸展树的根结点则p为它通过轻边连向的另一棵伸展树中的某一个点的编号（在原树中，就是该结点所在伸展树代表的链的最上层的那个节点的父结点），否则为该结点在伸展树中的父结点编号（通过重边相连）；
（2）在改接时删除边的时候，如果删除的是轻边则直接把父结点设为0即可，如果是重边则要sc一下再将父结点设为0；
（3）rot里面有一个地方很关键，极易疵！就是如果p是伸展树的根结点，则除了No的rf改为1，p的rf改为0之外，还要把No的父结点设为p的父结点；
（4）本题中不涉及整棵大树的根（就是root），如果需要root，则rot中还要加一句：if (root == p) root = No;
（5）cut里面有一种简便写法（不需要找到x的父结点的）：先access(x)，将x伸展到根之后，x及其右子树就是原树中以x为根的子树，左子树就是其它部分，所以直接将x与其左子结点断开即可（注意断开的是重边所以要sc一下，再将x的左子结点的父结点设为0、rf设为1，再upd一下）；
（6）一定要搞清楚rf的变化（该改时一定要改！）
最后，放上fanhq666超级大神的总结：
01