题目链接

题意：树上更新某一点权值，更新两点简单路径权值，查询最大，最小，和

思路：思路应该比较简单，就是树链剖分后用线段树维护区间最大最小以及区间和。

但是本题比较特殊的是给的边权，转化为点权即可。但是查询或者更新两点x,y之间路径的时候，x,y的lca点的点权对应的边是

fathar[lca]--->lca这条边，不属于x->y的简单路径。

所以在更新或者查询的时候，当处理到x,y属于同一条链的时候

这个过程说的是查询x->y，x,y一直往上跳，直到有一个跳到lca时（若dep[x]<dep[y]，x就是lca）

这时x,y属于一个连续区间，又因x点的权值不算，就是更新（dfn[x]+1,y)，dfn为时间戳

所以算是一道比较基础的树链剖分吧。

但是，这该死的码量，也太恶心了，我就写了一个bug,找了整两个小时?，wc

一个update1写成update我就真找不到。。。我太难了
 

//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
#define pii make_pair
#define pr pair<int,int>
//freopen("E://1.in","r",stdin);
//freopen("E://1.out","w",stdout);
typedef unsigned long long ull;
typedef long long ll;
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
//const int mod=1e9+7;
const int maxn=2e5+5;
int d[maxn],f[maxn],dfn[maxn],tim[maxn],top[maxn],size[maxn],son[maxn],a[maxn];
int head[maxn],sign;
char s[3];
struct node
{
    int to,p,val;
}edge[maxn<<1];
struct nod
{
    int mx,mi,sum;
}tree[maxn<<2];
int lazy[maxn<<2];
int n,t;
void init()
{
    for(int i=0;i<=n;i++) head[i]=-1;
    sign=t=0;
}
void add(int u,int v,int val)
{
    edge[sign]=node{v,head[u],val};
    head[u]=sign++;
}
void dfs1(int u,int pre,int step)
{
    d[u]=step;
    f[u]=pre;
    size[u]=1;
    for(int i=head[u];~i;i=edge[i].p)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        a[v]=edge[i].val;
        dfs1(v,u,step+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    dfn[u]=++t;
    tim[t]=u;
    top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    for(int i=head[u];~i;i=edge[i].p)
    {
        int v=edge[i].to;
        if(v!=f[u]&&v!=son[u]) dfs2(v,v);
    }
}
void pushup(int i,int l,int r)
{
    tree[i].sum=tree[lson].sum+tree[rson].sum;
    tree[i].mx=max(tree[lson].mx,tree[rson].mx);
    tree[i].mi=min(tree[lson].mi,tree[rson].mi);
}
void pushdown(int i,int l,int r)
{
    if(lazy[i])
    {
        tree[lson].sum=-tree[lson].sum;
        tree[rson].sum=-tree[rson].sum;
        int t1=tree[lson].mx,t2=tree[rson].mx,s1=tree[lson].mi,s2=tree[rson].mi;
        tree[lson].mx=-s1,tree[rson].mx=-s2,tree[lson].mi=-t1,tree[rson].mi=-t2;
        lazy[lson]^=1;
        lazy[rson]^=1;
        lazy[i]=0;
    }
}
void build(int i,int l,int r)
{
    if(l==r)
    {
        tree[i].sum=tree[i].mi=tree[i].mx=a[tim[l]];
        return ;
    }
    int mid=half;
    build(Lson);
    build(Rson);
    pushup(myself);
}
void update(int i,int l,int r,int x,int val)//单点更新
{
    if(l==r)
    {
        tree[i].sum=tree[i].mi=tree[i].mx=val;
        return;
    }
    int mid=half;
    pushdown(myself);
    if(x<=mid) update(Lson,x,val);
    else update(Rson,x,val);
    pushup(myself);
}
void update1(int i,int l,int r,int ql,int qr)//区间取反
{
    if(ql>qr) return;
    if(ql<=l&&qr>=r)
    {
        tree[i].sum=-tree[i].sum;
        lazy[i]=1-lazy[i];
        int x=tree[i].mi;
        tree[i].mi=-tree[i].mx;
        tree[i].mx=-x;
        return;
    }
    pushdown(myself);
    int mid=half;
    if(qr<=mid) update1(Lson,ql,qr);
    else if(ql>mid) update1(Rson,ql,qr);
    else update1(Lson,ql,mid),update1(Rson,mid+1,qr);
    pushup(myself);
}

int find_sum(int i,int l,int r,int ql,int qr)
{
    if(ql>qr) return 0;
    if(ql<=l&&qr>=r) return tree[i].sum;
    pushdown(myself);
    int mid=half;
    if(qr<=mid) return find_sum(Lson,ql,qr);
    else if(ql>mid) return find_sum(Rson,ql,qr);
    else return find_sum(Lson,ql,mid)+find_sum(Rson,mid+1,qr);
}
int find_max(int i,int l,int r,int ql,int qr)
{
    if(ql>qr) return -inff;
    if(ql<=l&&qr>=r) return tree[i].mx;
    pushdown(myself);
    int mid=half;
    if(qr<=mid) return find_max(Lson,ql,qr);
    else if(ql>mid) return find_max(Rson,ql,qr);
    else return max(find_max(Lson,ql,mid),find_max(Rson,mid+1,qr));
}
int find_min(int i,int l,int r,int ql,int qr)
{
    if(ql>qr) return inff;
    if(ql<=l&&qr>=r) return tree[i].mi;
    pushdown(myself);
    int mid=half;
    if(qr<=mid) return find_min(Lson,ql,qr);
    else if(ql>mid) return find_min(Rson,ql,qr);
    else return min(find_min(Lson,ql,mid),find_min(Rson,mid+1,qr));
}
void solve(int x,int y)//区间更新pre处理
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        update1(1,1,n,dfn[top[x]],dfn[x]);
        x=f[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    update1(1,1,t,dfn[x]+1,dfn[y]);
}
int get_max(int x,int y)
{
    int ans=-inff;
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        ans=max(ans,find_max(1,1,t,dfn[top[x]],dfn[x]));
        x=f[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    ans=max(ans,find_max(1,1,t,dfn[x]+1,dfn[y]));
    return ans;
    }
int get_min(int x,int y)
{
    int ans=inff;
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        ans=min(ans,find_min(1,1,t,dfn[top[x]],dfn[x]));
        x=f[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    ans=min(ans,find_min(1,1,t,dfn[x]+1,dfn[y]));
    return ans;
}
int get_sum(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        ans+=find_sum(1,1,t,dfn[top[x]],dfn[x]);
        x=f[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    ans+=find_sum(1,1,t,dfn[x]+1,dfn[y]);
    return ans;
}
int main()
{
//    freopen("E://2.in","r",stdin);
//    freopen("E://1.out","w",stdout);
    cin>>n;
    int x,y,val;
    init();
    for(int i=1;i<n;i++)
    {
        scanf("%d %d %d",&x,&y,&val);
        x++,y++;
        add(x,y,val),add(y,x,val);
    }
    dfs1(1,1,1);dfs2(1,1);build(1,1,n);
    int r;cin>>r;
    while(r--)
    {
        scanf("%s",s);
        scanf("%d %d",&x,&y);
        x++,y++;
        if(s[0]=='C') update(1,1,n,dfn[x],y-1);
        else if(s[0]=='N') solve(x,y);
        else if(s[2]=='M') printf("%d\n",get_sum(x,y));
        else if(s[2]=='X') printf("%d\n",get_max(x,y));
        else printf("%d\n",get_min(x,y));
    }
    return 0;
}