方法很简单，树剖，把区间提取出来，打翻转标记，再放回去。本来以为写起来也很简单T_T
注：由于某种原因，我写的是把题目中的r忽略掉的一般情况，否则写起来简单得多。
#include<bits/stdc++.h>
#define N 50005
#define M (s+t>>1)
#define L(t)(t)->c[0]
#define R(t)(t)->c[1]
#define Z(t)(L(t)->s+1)
using namespace std;
typedef long long ll;
struct edge{
int v;
edge*s;
}e[N*2];
edge*back=e,*h[N];
void add(int u,int v){
*back={v,h[u]};
h[u]=back++;
*back={u,h[v]};
h[v]=back++;
}
typedef int arr[N];
arr d,p,num,size,son,top;
void dfs1(int u){
d[u]=d[p[u]]+1;
size[u]=1;
int s=0;
for(edge*i=h[u];i;i=i->s)
if(i->v!=p[u]){
p[i->v]=u;
dfs1(i->v);
size[u]+=size[i->v];
if(s<size[i->v])
s=size[son[u]=i->v];
}
}
void dfs2(int u){
static int tot;
num[u]=++tot;
if(size[u]!=1){
top[son[u]]=top[u];
dfs2(son[u]);
}
for(edge*i=h[u];i;i=i->s)
if(i->v!=p[u]&&i->v!=son[u])
dfs2(top[i->v]=i->v);
}
struct node{
ll a[3];
int s,u,v;
bool rev;
node*c[2];
}mem[N];
node*last=mem,null[1]={0,1<<30},*root;
ll Sum(ll u,ll v){
return u+v;
}
ll Min(ll u,ll v){
return u<v?u:v;
}
ll Max(ll u,ll v){
return u<v?v:u;
}
ll(*f[3])(ll,ll)={
Sum,Min,Max
};
int devolve(node*t){
if(t==null)
return 0;
if(t->rev){
L(t)->rev^=1;
R(t)->rev^=1;
t->rev=0;
swap(L(t),R(t));
}
if(int u=t->u){
t->u=0;
L(t)->u+=u;
R(t)->u+=u;
t->a[1]+=u;
t->a[2]+=u;
t->v+=u;
t->a[0]+=u*t->s;
}
return Z(t);
}
node*update(node*t){
devolve(L(t));
devolve(R(t));
for(int i=0;i!=3;++i)
t->a[i]=f[i](f[i](L(t)->a[i],R(t)->a[i]),t->v);
t->s=R(t)->s+Z(t);
return t;
}
void link(bool i,node*&t,node*&s){
node*d=t->c[i];
t->c[i]=s;
s=update(t),t=d;
}
node*splay(int v,node*&t=root){
node*d[]={
null,null
};
while(v!=devolve(t)){
bool i=v>Z(t);
v-=i*Z(t);
if(v!=devolve(t->c[i])&&i==v>Z(t->c[i])){
v-=i*Z(t->c[i]);
link(i,t,t->c[i]->c[i^1]);
}
link(i,t,d[i]);
}
for(int i=0;i!=2;++i){
node*s=t->c[i^1];
while(d[i]!=null)
link(i,d[i],s);
t->c[i^1]=s;
}
return update(t);
}
node*&splay(int s,int t){
splay(s);
return L(splay(t-s+2,R(root)));
}
node*build(int s,int t){
if(s<=t){
node*i=last++;
L(i)=build(s,M-1);
R(i)=build(M+1,t);
return update(i);
}
return null;
}
struct vec{
int u,v,a;
vec(){}
vec(int u,int v):u(u),v(v),a(u){}
int size(){
return v-u+1;
}
}u[N],v[N];
int solve(int i,int j,vec*&u,vec*&v){
vec**s=&u,**t=&v;
for(;top[i]!=top[j];i=p[top[i]]){
if(d[top[i]]<d[top[j]])
swap(i,j),swap(s,t);
*(*s)++=vec(num[top[i]],num[i]);
}
if(d[i]<d[j])
swap(i,j),swap(s,t);
*(*s)++=vec(num[j],num[i]);
return num[j];
}
void amend(int p,int q,int j){
vec*s=u,*t=v;
solve(p,q,s,t);
while(s--!=u)
splay(s->u,s->v)->u+=j;
while(t--!=v)
splay(t->u,t->v)->u+=j;
}
ll query(int p,int q,int i){
ll j=i^1?0:1<<30;
vec*s=u,*t=v;
solve(p,q,s,t);
while(s--!=u)
j=f[i](j,splay(s->u,s->v)->a[i]);
while(t--!=v)
j=f[i](j,splay(t->u,t->v)->a[i]);
return j;
}
void invert(int p,int q){
node*j=null;
vec*s=u,*t=v;
solve(p,q,s,t);
vec*e=s;
while(t--!=v)
*e++=*t;
for(vec*i=u;i!=e;++i){
node*&a=splay(i->u,i->v);
a->rev=i<s;
L(splay(1,a))=j;
update(j=a);
a=null;
for(vec*z=u;z!=e;++z)
if(i->a<z->a){
z->u-=i->size();
z->v-=i->size();
}
}
j->rev=1;
for(vec*i=u;i!=e;++i){
node*&a=splay(i->u,i->u-1);
a=j;
j=R(splay(i->size(),a));
a->rev=i<s;
R(a)=null;
update(a);
for(vec*z=u;z!=e;++z)
if(i->a<z->a){
z->u+=i->size();
z->v+=i->size();
}
}
}
int main(){
int n,m,s,t,u;
char a[10];
scanf("%d%d%*d",&n,&m);
root=build(0,n+1);
for(int i=1;i!=n;++i){
scanf("%d%d",&s,&t);
add(s,t);
}
dfs1(1);
dfs2(top[1]=1);
while(m--){
scanf("%s%d%d",a,&s,&t);
if(a[2]=='v')
invert(s,t);
else if(a[2]=='c'){
scanf("%d",&u);
amend(s,t,u);
}else
printf("%lld
",query(s,t,a[2]=='j'?2:a[2]!='m'));
}
}