【背景】
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