Link - Cut Trees 裸题。。。（Link-Cut Trees 戳这里） 若可以从i弹到j则连一条从j到i的边，若弹飞了，则连一条从0到i的边。。。 然后就是这样。。。 代码如下：
/* ID: Sunshine_cfbsl LANG: C++ */ #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN = 200010; int n, m; struct LCT { bool root[MAXN]; int fa[MAXN], ch[MAXN][2], size[MAXN]; void init() { memset(fa, 0, sizeof(fa)); memset(ch, 0, sizeof(ch)); memset(root, true, sizeof(root)); } void maintain(int p) { size[p] = size[ch[p][0]]+size[ch[p][1]]+1; } void Rotate(int p, bool t) { int f = fa[p]; fa[ch[f][t^1] = ch[p][t]] = f; if(!root[f]) ch[fa[f]][ch[fa[f]][1]==f] = p; else root[p] = !(root[f] = false); fa[p] = fa[f]; ch[fa[f] = p][t] = f; maintain(f); } void splay(int x) { while(!root[x]) { int p = fa[x]; if(root[p]) { Rotate(x, x==ch[p][0]); break; } bool f = x==ch[p][0], f1 = p==ch[fa[p]][0], f2 = p==ch[fa[p]][1]; Rotate(f?f1?p:x:f2?p:x, f); Rotate(x, f1); } maintain(x); } void access(int u) { int v = 0; while(u) { splay(u); root[ch[u][1]] = true; root[v] = false; ch[u][1] = v; maintain(u); u = fa[v = u]; } } void cut(int v) { access(v); splay(v); root[ch[v][0]] = true; ch[v][0] = fa[ch[v][0]] = 0; } void link(int v, int w) { cut(v); fa[v] = w; maintain(v); } }trees; int main() { int i, tmp, x, y; scanf("%d", &n); trees.init(); for(i = 1; i <= n; i++) { scanf("%d", &tmp); trees.fa[i] = i+tmp>n?0:i+tmp; trees.size[i] = 1; } scanf("%d", &m); for(i = 1; i <= m; i++) { scanf("%d%d", &x, &y); y++; if(x == 1) { trees.access(y); trees.splay(y); printf("%d\n", trees.size[trees.ch[y][0]]+1); } else { scanf("%d", &x); trees.link(y, y+x>n?0:y+x); } } return 0; }