题目大意：

　　给你一棵树，一开始每个点的权值都是0，要求支持一下三种操作：

　　　　1.路径加等差数列。

　　　　2.路径求和。

　　　　3.回到以前的某次操作。

　　强制在线。

思路：

　　树链剖分+主席树。

　　最坏情况下，n个点的树最多会被分成n-1个链，

　　这里不能每个点都开一个主席树，因为主席树中要存每个线段树的根结点编号，总共有m次操作，

　　因此最坏情况下，总共要存nm个根结点，显然会爆空间，因此我们可以考虑将所有点合并在一个主席树中。

　　路径加等差数列时，我们可以先求出两个端点x和y上加的值ax和ay，然后往上爬的过程中根据跳过的长度维护ax和ay即可。

　　交换x和y的时候就相当于翻转等差数列，只要交换ax和ay并对公差b取反即可。

　　然后随随便便就跑了Rank2（Rank2的vjudge7和Rank3的skylee都是我的程序），0.63s。

　　后来想抢Rank发现刷不上去了（似乎CodeChef是根据第一次交的程序来排名的）。

　　交的时候发现忘记处理强制在线的操作也能AC？

细节：

　　题目中回退操作以后并不能删掉中间被跳过的操作，比如从第四次操作回退到第三次操作，如果再进行一次修改，那么这个修改操作就是第五次操作。

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 inline int getint() {  6     char ch;  7     while(!isdigit(ch=getchar()));  8     int x=ch^'0';  9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10     return x; 11 } 12 const int V=100001,logV=200,M=100001; 13 std::vector
         
           e[V]; 14 inline void add_edge(const int u,const int v) { 15     e[u].push_back(v); 16 } 17 int par[V],size[V],son[V],top[V],dep[V],id[V],cnt; 18 void dfs1(const int x,const int p) { 19     dep[x]=dep[p]+1; 20     par[x]=p; 21     size[x]=1; 22     for(unsigned i=0;i
          
           size[son[x]]) son[x]=y; 28 } 29 } 30 void dfs2(const int x) { 31 top[x]=x==son[par[x]]?top[par[x]]:x; 32 id[x]=++cnt; 33 if(son[x]) dfs2(son[x]); 34 for(unsigned i=0;i
           
            >1; 66 if(l<=mid) modify(left[p],left[old_p],b,mid,l,std::min(mid,r),x,y); 67 if(r>mid) modify(right[p],right[old_p],mid+1,e,std::max(mid+1,l),r,x+(std::max(mid+1,l)-l)*y,y); 68 if(!left[p]) left[p]=left[old_p]; 69 if(!right[p]) right[p]=right[old_p]; 70 push_up(p,b,e); 71 } 72 long long query(const int p,const int b,const int e,const int l,const int r) { 73 if(!p) return 0; 74 if((b==l)&&(e==r)) return sum[p]; 75 int mid=(b+e)>>1; 76 long long ret=(first[p]*2+(l+r-b*2)*diff[p])*(r-l+1)/2; 77 if(l<=mid) ret+=query(left[p],b,mid,l,std::min(mid,r)); 78 if(r>mid) ret+=query(right[p],mid+1,e,std::max(mid+1,l),r); 79 return ret; 80 } 81 }; 82 FotileTree t; 83 inline int get_lca(int x,int y) { 84 while(top[x]!=top[y]) { 85 if(dep[top[x]]
            
             dep[y]) std::swap(x,y); 89 return x; 90 } 91 int n; 92 inline void modify(const int old_root,int &root,int x,int y,const long long a,long long b) { 93 int lca=get_lca(x,y); 94 int dis=dep[x]+dep[y]-dep[lca]*2; 95 int ax=a,ay=a+b*dis; 96 while(top[x]!=top[y]) { 97 if(dep[top[x]]