【背景】
2012年1月19日，本沙茶開(kāi)始看動(dòng)態(tài)樹(shù)論文，搞懂了一些；
2012年1月20日，開(kāi)始寫動(dòng)態(tài)樹(shù)，使用的題是QTREE，花了整整一天時(shí)間總算寫完，交上去，TLE……
2012年1月21日，又調(diào)了一天，對(duì)拍了100+組隨機(jī)數(shù)據(jù)都瞬間出解，交上去，還是TLE……
2012年2月8日，WC2012，fanhq666講動(dòng)態(tài)樹(shù)，又搞懂了一點(diǎn)，于是當(dāng)天晚上回房間以后就開(kāi)始繼續(xù)調(diào)，交上去，TLE……
2012年2月9日，晚上繼續(xù)調(diào)QTREE，TLE……
在挑戰(zhàn)動(dòng)態(tài)樹(shù)N次失敗之后，本沙茶昨天再次去挑戰(zhàn)動(dòng)態(tài)樹(shù)……這次換了一個(gè)題：
BZOJ2002（傳說(shuō)中的動(dòng)態(tài)樹(shù)模板題）
一開(kāi)始還是TLE了，不過(guò)后來(lái)把數(shù)據(jù)搞到手以后，發(fā)現(xiàn)TLE的原因并不是常數(shù)大，而是死循環(huán)了，最后，經(jīng)過(guò)2h+的調(diào)試，總算找到了錯(cuò)誤（有好幾處），終于AC了……
【關(guān)于BZOJ2002】
從每個(gè)點(diǎn)i往(i+Ki)連一條邊，如果(i+Ki)不存在則往一個(gè)附加的結(jié)點(diǎn)（本沙茶的代碼中為1號(hào)點(diǎn)，因?yàn)?號(hào)點(diǎn)是不能使用的）連一條邊，這樣就是一棵樹(shù)（除1號(hào)點(diǎn)外，每個(gè)點(diǎn)有且只有一個(gè)后繼……），然后，問(wèn)題中的兩種操作就是“改接”和“詢問(wèn)到根的距離”，可以用動(dòng)態(tài)樹(shù)搞；
【代碼】
#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;
}
【易疵點(diǎn)】
（1）注意一個(gè)點(diǎn)的父結(jié)點(diǎn)p有兩種可能：如果該結(jié)點(diǎn)是某棵伸展樹(shù)的根結(jié)點(diǎn)則p為它通過(guò)輕邊連向的另一棵伸展樹(shù)中的某一個(gè)點(diǎn)的編號(hào)（在原樹(shù)中，就是該結(jié)點(diǎn)所在伸展樹(shù)代表的鏈的最上層的那個(gè)節(jié)點(diǎn)的父結(jié)點(diǎn)），否則為該結(jié)點(diǎn)在伸展樹(shù)中的父結(jié)點(diǎn)編號(hào)（通過(guò)重邊相連）；
（2）在改接時(shí)刪除邊的時(shí)候，如果刪除的是輕邊則直接把父結(jié)點(diǎn)設(shè)為0即可，如果是重邊則要sc一下再將父結(jié)點(diǎn)設(shè)為0；
（3）rot里面有一個(gè)地方很關(guān)鍵，極易疵！就是如果p是伸展樹(shù)的根結(jié)點(diǎn)，則除了No的rf改為1，p的rf改為0之外，還要把No的父結(jié)點(diǎn)設(shè)為p的父結(jié)點(diǎn)；
（4）本題中不涉及整棵大樹(shù)的根（就是root），如果需要root，則rot中還要加一句：if (root == p) root = No;
（5）cut里面有一種簡(jiǎn)便寫法（不需要找到x的父結(jié)點(diǎn)的）：先access(x)，將x伸展到根之后，x及其右子樹(shù)就是原樹(shù)中以x為根的子樹(shù)，左子樹(shù)就是其它部分，所以直接將x與其左子結(jié)點(diǎn)斷開(kāi)即可（注意斷開(kāi)的是重邊所以要sc一下，再將x的左子結(jié)點(diǎn)的父結(jié)點(diǎn)設(shè)為0、rf設(shè)為1，再upd一下）；
（6）一定要搞清楚rf的變化（該改時(shí)一定要改?。?br />
最后，放上fanhq666超級(jí)大神的總結(jié)：
01