小Y家里有一个大森林，里面有n棵树，编号从1到n。一开始这些树都只是树苗，只有一个节点，标号为1。这些树都有一个特殊的节点，我们称之为生长节点，这些节点有生长出子节点的能力。

小Y掌握了一种魔法，能让第l棵树到第r棵树的生长节点长出一个子节点。同时她还能修改第l棵树到第r棵树的生长节点。她告诉了你她使用魔法的记录，你能不能管理她家的森林，并且回答她的询问呢？

参考：

思路：

显然我们不能对每棵树LCT维护一下，而且我们对于这棵树的形态还很严格。

那么我们把前一棵树的形态转换为后一棵树的形态，这样就只需要一棵树了。

先考虑对于0操作，实际上我们可以记录每个时刻每个节点在哪一段区间中（代码的L和R就是干这个的），所以我们大可以对所有的树都进行0操作。

对于1操作，和0操作类似，用L和R更新l和r后进行操作。

然后为了能够快捷的更新树，我们建立一个size为0的虚点（这样对于路径长度就不需要修改了），所有的生长操作都在上面进行，这样我们删除的时候cut这个点即可。

对于2操作，事实上两个点一定存在的话，完全可以让0和1操作全部排到它的前面。

实现：

先把所有操作存下来，然后以操作的树为第一关键字，操作编号和顺序为第二关键字排序。

（对于区间修改思考差分，毕竟我们都是对同一棵树操作的。）

然后按树编号从左到右进行操作，对于0和1操作先对虚点清空然后长即可。

查询的时候就是用LCA求最短路的方法一样。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int N=4e5+5;struct data{ int pos,id,from,to;}qry[N];int n,m,fa[N],tr[N][2],val[N],size[N];int cnt,tot,sum,aux,L[N],R[N],id[N],ans[N];inline bool cmp(data a,data b){ return a.pos
             
              
               0){ ans[qry[i].id]=0; access(qry[i].from);splay(qry[i].from); ans[qry[i].id]+=size[qry[i].from]; int lca=access(qry[i].to); splay(qry[i].to); ans[qry[i].id]+=size[qry[i].to]; access(lca);splay(lca);ans[qry[i].id]-=size[lca]*2; } else{ cut(qry[i].from);link(qry[i].from,qry[i].to); } i++; } } for(int i=1;i<=m;i++){ if(ans[i]>=0)printf("%d\n",ans[i]); } return 0;}
              
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++