解题思路

　　跟这道题很像。只是有了一个询问\(2\)的操作，然后询问\(2\)的答案其实就是\(val[x]+val[y]-2*val[lca(x,y)]+1\)(画图理解)。剩下的操作跟那道题就一样了。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXN = 100005;inline int rd(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f?x:-x;}int n,m,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1];int dep[MAXN],siz[MAXN],fa[MAXN],Fa[MAXN],L[MAXN];int top[MAXN],id[MAXN],wt[MAXN],num,son[MAXN];int Max[MAXN<<2],ll[MAXN],tag[MAXN<<2];inline int max(int x,int y){ return x>y?x:y;}inline void add(int bg,int ed){ to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;}void dfs1(int x,int f,int d){ fa[x]=f;siz[x]=1;dep[x]=d;ll[x]=x;Fa[x]=f; int maxson=-1,u; for(int i=head[x];i;i=nxt[i]){ u=to[i];if(u==f) continue; dfs1(u,x,d+1);siz[x]+=siz[u]; if(siz[u]>maxson) {maxson=siz[u];son[x]=u;} }}void dfs2(int x,int topf){ top[x]=topf;id[x]=++num;wt[num]=dep[x]; if(!son[x]) return;dfs2(son[x],topf);int u; for(int i=head[x];i;i=nxt[i]){ u=to[i];if(u==son[x] || u==fa[x]) continue; dfs2(u,u); }}inline void pushdown(int x){ Max[x<<1]+=tag[x];Max[x<<1|1]+=tag[x]; tag[x<<1]+=tag[x];tag[x<<1|1]+=tag[x]; tag[x]=0;}void build(int x,int l,int r){ if(l==r) {Max[x]=wt[l];return;}int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); Max[x]=max(Max[x<<1],Max[x<<1|1]);}void update(int x,int l,int r,int L,int R,int k){ if(L<=l && r<=R) { Max[x]+=k;tag[x]+=k; return ; }int mid=(l+r)>>1;if(tag[x]!=0) pushdown(x); if(L<=mid) update(x<<1,l,mid,L,R,k); if(mid
          
           dep[top[y]]) x=Fa[top[x]]; else y=Fa[top[y]]; } return dep[x]
           
            >1;if(tag[x]!=0) pushdown(x); if(L<=mid) return query(x<<1,l,mid,L); else return query(x<<1|1,mid+1,r,L);}inline int qRange(int x,int y){ return query(1,1,n,id[x])+query(1,1,n,id[y])-2*query(1,1,n,id[lca(x,y)])+1;}int query_max(int x,int l,int r,int L,int R){ if(L<=l && r<=R) return Max[x]; int mid=(l+r)>>1,ret=0;if(tag[x]!=0) pushdown(x); if(L<=mid) ret=max(ret,query_max(x<<1,l,mid,L,R)); if(mid