这个题目前有两种做法，一个是FHQ-Treap维护树剖，一个是FHQ-Treap+LCT，无论是哪个，都很考验思维力和码力，不仅比较难想，而且比较难调，让大家直观看一下码量：

#include<bits/stdc++.h>
#define int long long
using namespace std;
char ch;
bool ok;
void read(int &x){
    for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;
    for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    if (ok) x=-x;
}
const int maxn=50005;
char s[10];
int n,q,r,x,y,v;
int random(int lim){return rand()%lim+1;}
typedef pair<int,int> PII;
struct node{
    int siz;
    int val,maxv,minv,sum;
    void add(int v){
	    val+=v;
		maxv+=v;
		minv+=v;
		sum+=v*siz;
	}
    void init(){
	    maxv=minv=sum=val;
		siz=1;
	}
    void update(const node &x){
	    siz+=x.siz;
		maxv=max(maxv,x.maxv);
		minv=min(minv,x.minv);
		sum+=x.sum;
	}
};
struct treep{
    node p[maxn];
    int son[maxn][2],rev[maxn],add[maxn];
    void reverse(int x){if (x) rev[x]^=1;}
    void addtag(int x,int v){
	    if(x){
	    	add[x]+=v;
			p[x].add(v);
		}
	}
    void pushdown(int x){
        if(rev[x]){
        	swap(son[x][0],son[x][1]);
			reverse(son[x][0]);
			reverse(son[x][1]);
			rev[x]=0;
		}
        if(add[x]){
        	addtag(son[x][0],add[x]);
			addtag(son[x][1],add[x]);
			add[x]=0;
		}
    }
    void update(int x){
        p[x].init();
        if (son[x][0]) p[x].update(p[son[x][0]]);
        if (son[x][1]) p[x].update(p[son[x][1]]);
    }
    PII split(int x,int k){
        if (!k) return make_pair(0,x);
        if (p[x].siz==k) return make_pair(x,0);
        PII tmp; pushdown(x);
        if (k<=p[son[x][0]].siz){
            tmp=split(son[x][0],k),son[x][0]=tmp.second,update(x);
            return make_pair(tmp.first,x);
        }else{
            tmp=split(son[x][1],k-p[son[x][0]].siz-1),son[x][1]=tmp.first,update(x);
            return make_pair(x,tmp.second);
        }
    }
    int merge(int x,int y){
        if (!x||!y) return x+y;
        pushdown(x);
		pushdown(y);
        if (random(p[x].siz+p[y].siz)<=p[x].siz){
            son[x][1]=merge(son[x][1],y);
			update(x);
            return x;
        }
        else{
            son[y][0]=merge(x,son[y][0]);
			update(y);
            return y;
        }
    }
}T;
struct LCT{
    int fa[maxn],son[maxn][2],rev[maxn],root[maxn],siz[maxn];
    void init(int n){
	    for (int i=1;i<=n;i++) root[i]=i;
	}
    int which(int x){
	    return son[fa[x]][1]==x;
	}
    bool isroot(int x){
	    return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
	}
    void reverse(int x){
	    rev[x]^=1;
	}
    void pushdown(int x){
    	if(!rev[x]) return;
	    swap(son[x][0],son[x][1]);
		reverse(son[x][0]);
		reverse(son[x][1]);
		rev[x]=0;
	}
    void relax(int x){
	    if (!isroot(x)) relax(fa[x]); 
		pushdown(x);
     }
    void update(int x){
        siz[x]=1;
        if (son[x][0]) siz[x]+=siz[son[x][0]];
        if (son[x][1]) siz[x]+=siz[son[x][1]];
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],d=which(x),dd=which(y);
        fa[son[x][d^1]]=y;
		son[y][d]=son[x][d^1];
		fa[x]=fa[y];
        if (!isroot(y)) son[z][dd]=x;
        son[x][d^1]=y;
		fa[y]=x;
		update(y);
		update(x);
    }
    void splay(int x){
        relax(x);
        int t;
        for (t=x;!isroot(t);t=fa[t]);
        swap(root[t],root[x]);
        while (!isroot(x)){
            if (isroot(fa[x])) rotate(x);
            else if (which(x)==which(fa[x])) rotate(fa[x]),rotate(x);
            else rotate(x),rotate(x);
        }
    }
    void access(int x){
        for (int p=0;x;x=fa[x]){
            splay(x);
            if (son[x][1]){
                PII tmp=T.split(root[x],siz[son[x][0]]+1);
                root[x]=tmp.first,root[son[x][1]]=tmp.second;
            }
            if (p) root[x]=T.merge(root[x],root[p]),root[p]=0;
            son[x][1]=p,fa[p]=x,update(p=x);
        }
    }
    void make_root(int x){
	    access(x);
		splay(x);
		reverse(x);
		T.reverse(root[x]);
	}
    void link(int x,int y){
	    make_root(x);
		fa[x]=y;
	}
    void reverse(int x,int y){
	    make_root(x);
		access(y);
		splay(y);
		T.reverse(root[y]);
	}
    void addtag(int x,int y,int v){
		make_root(x);
		access(y);
		splay(y);
		T.addtag(root[y],v);
	}
    int query_max(int x,int y){
	    make_root(x);
		access(y),splay(y);
		return T.p[root[y]].maxv;
	}
    int query_min(int x,int y){
		make_root(x);
		access(y);
		splay(y);
		return T.p[root[y]].minv;
	}
    int query_sum(int x,int y){
	    make_root(x);
		access(y);
		splay(y);
		return T.p[root[y]].sum;
	}
}lct;
signed main(){
	srand(time(0));
    read(n),read(q),read(r),lct.init(n);
    for (int i=1;i<=n;i++){
    	T.p[i].val=0;
		T.p[i].init();
	}
    for (int i=1;i<n;i++) read(x),read(y),lct.link(x,y);
    while (q--){
        scanf("%s",s);
		read(x);
		read(y);
        if (s[2]=='c'){
        	read(v);
			lct.addtag(x,y,v);
		}else if (s[2]=='m'){
        	printf("%lld\n",lct.query_sum(x,y));
		}
        else if (s[2]=='j'){
        	printf("%lld\n",lct.query_max(x,y));
		}else if (s[2]=='n'){
			printf("%lld\n",lct.query_min(x,y));
		}else if(s[2]=='v'){
        	lct.reverse(x,y);
		}
    }
    return 0;
}
这不得有黑？