传送门
每个点都会跳到另一个点，连边就是一棵树。
更改弹力就是换边。
求一个点跳多少次跳到终点就是求这个点的深度，那么只需要维护 size 域，access(n + 1) 然后 splay(x)，求 size[son[x][0]] 即可，
因为 splay 是以深度为关键字的，所以左端点就是深度比它小的。
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define N 200010 4 #define min(x, y) ((x) < (y) ? (x) : (y)) 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 #define swap(x, y) ((x) ^= (y) ^= (x) ^= (y)) 7 #define get(x) (son[f[x]][1] == (x)) 8 #define isroot(x) (son[f[x]][0] ^ (x) && son[f[x]][1] ^ (x)) 9 10 int n, k; 11 int a[N], f[N], size[N], rev[N], son[N][2], s[N]; 12 13 inline int read() 14 21 22 inline void update(int x) 23 30 } 31 32 inline void pushdown(int x) 33 41 } 42 43 inline void rotate(int x) 44 60 61 inline void splay(int x) 62 71 72 inline void access(int x) 73 76 77 inline void reverse(int x) 78 83 84 inline void cut(int x, int y) 85 92 93 inline void link(int x, int y) 94 99 100 inline int query(int x) 101 107 108 int main() 109 118 size[n + 1] = 1; 119 k = read(); 120 for(i = 1; i <= k; i++) 121 131 } 132 return 0; 133 }View Code
上一篇：[POJ1611]The Suspects（并查集）
下一篇：火星探险问题
LCT
