弹飞绵羊LCT

　　题意：

　　一共n个位置，每个位置一个属性k［i］，表示在i位置会被瞬间转移到i+k［i］（然后又依次转移）。问从一个点开始多少次会出界。并且支持修改k［i］。

　　题解：

　　把i向i+k［i］连边，若i+k［i］出界就向外面的总根连边。询问就是求深度。

　　把一个节点splay到根之后（前提是根是原树最开始的根），左边一定是比它浅的（且一定是它到原树根的一条链（因为access操作）），所以左儿子的size就是它的深度（根的深度为0）。

　　居然以前要写一天的LCT半个小时就写好了，要不是BZOJ的编译器栈空间不够就1A了

　　/**************************************************************

　　Problem： 2002

　　User： Lazer2001

　　Language： C++

　　Result： Accepted

　　TIme:1988 ms

　　Memory:22324 kb

　　****************************************************************/

　　# include 《bits/stdc++.h》

　　inline int read （ ） {

　　register int x， c ;

　　while （ isspace （ c = getchar （ ） ） ） ;

　　for （ x = -48 + c ; isdigit （ c = getchar （ ） ） ; （ x *= 10 ） += c - 48 ） ;

　　return x ;

　　}

　　template 《 class T 》 inline T min （ const T& a， const T& b ） { return a 《 b ？ a ： b ; }

　　template 《 class T 》 inline void swap （ T& a， T& b ） { T c （ a ） ; a = b， b = c ; }

　　# define N 200010

　　class LinkCutTree {

　　private ：

　　struct node {

　　int siz ;

　　bool rev_flag ;

　　node *ch ［2］， *fa ;

　　inline void update （ ） {

　　siz = ch ［0］ -》 siz + ch ［1］ -》 siz + 1 ;

　　}

　　} pool ［N 《《 1］， *root ［N］， *null ;

　　int n ;

　　inline void push_down （ node*& p ） {

　　if （ p -》 rev_flag ） {

　　swap （ p -》 ch ［0］， p -》 ch ［1］ ） ;

　　if （ p -》 ch ［0］ ！= null ） p -》 ch ［0］ -》 rev_flag ^= 1 ;

　　if （ p -》 ch ［1］ ！= null ） p -》 ch ［1］ -》 rev_flag ^= 1 ;

　　p -》 rev_flag = 0 ;

　　}

　　}

　　inline node* newnode （ node*& fa ） {

　　staTIc node* tp （ pool + 1 ） ;

　　tp -》 siz = 1 ; tp -》 rev_flag = 0 ;

　　return tp -》 fa = fa， tp -》 ch ［0］ = tp -》 ch ［1］ = null， tp ++ ;

　　}

　　# define isroot（ p ） （ p -》 fa == null || （ p -》 fa -》 ch ［0］ ！= p && p -》 fa -》 ch ［1］ ！= p ） ）

　　# define isrs（ p ） （ p == p -》 fa -》 ch ［1］ ）

　　inline void rotate （ node* p ） {

　　if （ p == null || isroot （ p ） ） return ;

　　bool d （ isrs （ p ） ） ;

　　node* par = p -》 fa ;

　　par -》 ch ［d］ = p -》 ch ［！ d］ ;

　　if （ p -》 ch ［！ d］ ！= null ） p -》 ch ［！ d］ -》 fa = par ;

　　if （ ！ isroot （ par ） ） par -》 fa -》 ch ［isrs （ par ）］ = p ; // ！isroot（par）

　　p -》 fa = par -》 fa ;

　　par -》 fa = p ;

　　p -》 ch ［！ d］ = par ;

　　par -》 update （ ） ; p -》 update （ ） ;

　　}

　　node* st ［N 《《 1］ ;

　　inline void splay （ node* p ） {

　　if （ p == null ） return ;

　　// staTIc node* st ［N 《《 1］ ; staTIc int tp （ 0 ） ; RE！！！！

　　int tp ;

　　st ［tp = 1］ = p ;

　　for （ node* t = p ; ！ isroot （ t ） ; t = t -》 fa ） st ［++ tp］ = t -》 fa ;

　　while （ tp ） push_down （ st ［tp --］ ） ;

　　while （ ！ isroot （ p ） ） {

　　if （ isrs （ p ） == isrs （ p -》 fa ） && ！ isroot （ p -》 fa ） ） rotate （ p -》 fa ） ;

　　rotate （ p ） ;

　　}

　　}