/*
luogu1505
非常简单的处理边权的树剖题。
在树上将一条边定向，把这条边的权值赋给这条边的出点
树剖的时候不计算lca权值即可
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int h=200010;
//线段树部分
ll a[h];
struct node{
int l,r;
ll val,mx,mn;
ll lz;
}tree[h*4];
void pushup(int root){
tree[root].val=tree[root*2].val+tree[root*2+1].val;
tree[root].mx=max(tree[root*2].mx,tree[root*2+1].mx);
tree[root].mn=min(tree[root*2].mn,tree[root*2+1].mn);
}
void build(int root,int l,int r){
tree[root].l=l,tree[root].r=r,tree[root].lz=1;
tree[root].mx=-1010,tree[root].mn=1010;
if(l==r){
tree[root].mx=a[l];
tree[root].mn=a[l];
tree[root].val=a[l];
return;
}
int mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid+1,r);
pushup(root);
}
void pushdown(int root){//存储区间取反
if(tree[root].lz==1)
return;
tree[root*2].val*=tree[root].lz;
tree[root*2+1].val*=tree[root].lz;
swap(tree[root*2].mx,tree[root*2].mn);
tree[root*2].mx*=-1;
tree[root*2].mn*=-1;
swap(tree[root*2+1].mx,tree[root*2+1].mn);
tree[root*2+1].mx*=-1;
tree[root*2+1].mn*=-1;
tree[root*2].lz*=tree[root].lz;
tree[root*2+1].lz*=tree[root].lz;
tree[root].lz=1;
}
ll query_sum(int root,int l,int r){//区间和
if(tree[root].l>=l&&tree[root].r<=r)
return tree[root].val;
pushdown(root);
int mid=(tree[root].l+tree[root].r)/2;
ll ans=0;
if(mid>=l)
ans+=query_sum(root*2,l,r);
if(mid<r)
ans+=query_sum(root*2+1,l,r);
return ans;
}
ll query_max(int root,int l,int r){//区间最大
if(tree[root].l>=l&&tree[root].r<=r)
return tree[root].mx;
pushdown(root);
int mid=(tree[root].l+tree[root].r)/2;
ll ans=-1010;//这里要设成负数，因为边的权值可能全是负数
if(mid>=l)
ans=max(ans,query_max(root*2,l,r));
if(mid<r)
ans=max(ans,query_max(root*2+1,l,r));
return ans;
}
ll query_min(int root,int l,int r){//区间最小
if(tree[root].l>=l&&tree[root].r<=r)
return tree[root].mn;
pushdown(root);
int mid=(tree[root].l+tree[root].r)/2;
ll ans=1010;
if(mid>=l)
ans=min(ans,query_min(root*2,l,r));
if(mid<r)
ans=min(ans,query_min(root*2+1,l,r));
return ans;
}
void change(int root,int p,ll x){//单点修改
if(tree[root].l==tree[root].r){
tree[root].mx=tree[root].mn=tree[root].val=x;
return;
}
pushdown(root);
int mid=(tree[root].l+tree[root].r)/2;
if(mid>=p)
change(root*2,p,x);
else
change(root*2+1,p,x);
pushup(root);
}
void turn(int root,int l,int r){//区间取反
if(tree[root].l>=l&&tree[root].r<=r){
tree[root].mx*=-1,tree[root].mn*=-1;
swap(tree[root].mx,tree[root].mn);
tree[root].val*=-1;
tree[root].lz*=-1;
return;
}
pushdown(root);
int mid=(tree[root].l+tree[root].r)/2;
if(mid>=l)
turn(root*2,l,r);
if(mid<r)
turn(root*2+1,l,r);
pushup(root);
}
int head[h],last[h],to[h],tot=0;
void add_edge(int x,int y){
tot++;
last[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void add(int x,int y){
add_edge(x,y);
add_edge(y,x);
}
int n,m,roots;
//树剖部分
ll w[h];
int fa[h],siz[h],dep[h],mxs[h],dfn[h],top[h],td=0;
void dfs1(int now,int f){
fa[now]=f,siz[now]=1;
for(int i=head[now];i;i=last[i]){
int nex=to[i];
if(nex==f)
continue;
dep[nex]=dep[now]+1;
dfs1(nex,now);
siz[now]+=siz[nex];
if(siz[nex]>siz[mxs[now]]||!mxs[now])
mxs[now]=nex;
}
}
void dfs2(int now,int from){
dfn[now]=++td,a[td]=w[now],top[now]=from;
if(mxs[now])
dfs2(mxs[now],from);
for(int i=head[now];i;i=last[i]){
int nex=to[i];
if(nex==fa[now]||nex==mxs[now])
continue;
dfs2(nex,nex);
}
}
void pturn(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
turn(1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
if(x!=y)
turn(1,dfn[x]+1,dfn[y]);//这一步操作左端是dfn[x]+1，因为lca的权值代表的边不在路径内
}
ll pquery_sum(int x,int y){
ll ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ans+=query_sum(1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
if(x!=y)
ans+=query_sum(1,dfn[x]+1,dfn[y]);//同上
return ans;
}
ll pquery_min(int x,int y){
ll ans=1010;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ans=min(ans,query_min(1,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
if(x!=y)
ans=min(ans,query_min(1,dfn[x]+1,dfn[y]));
return ans;
}
ll pquery_max(int x,int y){
ll ans=-1010;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])//这里注意里面是top
swap(x,y);
ans=max(ans,query_max(1,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
if(x!=y)
ans=max(ans,query_max(1,dfn[x]+1,dfn[y]));
return ans;
}
struct edge{
int p1,p2,out;
ll len;
}e[h];
int main(){
scanf("%d",&n);
//题目里的点从0开始，我们为了方便操作，将所有点加1，从1开始
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u+1,v+1);
e[i].p1=u+1,e[i].p2=v+1;
scanf("%lld",&e[i].len);
}
dfs1(1,0);
for(int i=1;i<n;i++){//给边定向
if(fa[e[i].p2]==e[i].p1)
e[i].out=e[i].p2,w[e[i].p2]=e[i].len;
else
e[i].out=e[i].p1,w[e[i].p1]=e[i].len;
}
dfs2(1,1);
build(1,1,td);
scanf("%d",&m);
for(int i=1;i<=m;i++){
string op;
cin>>op;
if(op=="C"){
int ed;
ll ch;
scanf("%d%lld",&ed,&ch);
change(1,dfn[e[ed].out],ch);
}
if(op=="N"){
int x,y;
scanf("%d%d",&x,&y);
pturn(x+1,y+1);
}
if(op=="SUM"){
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",pquery_sum(x+1,y+1));
}
if(op=="MAX"){
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",pquery_max(x+1,y+1));
}
if(op=="MIN"){
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",pquery_min(x+1,y+1));
}
}
return 0;
}
luoguP1505旅游（处理边权的树剖）的相关教程结束。
