mxqz slpf

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=2e5+7;
ll top[Maxn],sz[Maxn],dep[Maxn],wt[Maxn],cnt,id[Maxn],tot,head[Maxn],fa[Maxn],son[Maxn],seq[Maxn];
ll n,q;
struct edge1{
    ll u,v,w,Next;
}Edge[Maxn<<1];
inline void add(ll u,ll v,ll w){
    Edge[++tot]=(edge1){u,v,w,head[u]};head[u]=tot;
}
struct SegMent{
    ll l,r,mx;
}tree[Maxn<<1];
void dfs_dep(ll u,ll father){
    dep[u]=dep[father]+1;
    fa[u]=father;
    sz[u]=1;
    ll maxson=-1;
    for(ll i=head[u];i;i=Edge[i].Next)
        if(Edge[i].v!=father){
            wt[Edge[i].v]=Edge[(i+1)/2].w;
            dfs_dep(Edge[i].v,u);
            sz[u]+=sz[Edge[i].v];
            if(sz[Edge[i].v]>maxson) maxson=sz[Edge[i].v],son[u]=Edge[i].v;
        }
}
void dfs_new(ll x,ll topx){
    id[x]=++cnt;
    top[x]=topx;
    seq[cnt]=x;
    if(!son[x]) return ;
    dfs_new(son[x],topx);
    for(ll i=head[x];i;i=Edge[i].Next){
        if(Edge[i].v==fa[x]||Edge[i].v==son[x]) continue;
        dfs_new(Edge[i].v,Edge[i].v);
    }
}
inline void pushup(ll node){
    tree[node].mx=max(tree[node<<1].mx,tree[node<<1|1].mx);
}
inline void buildtree(ll node,ll l,ll r){
    tree[node].l=l,tree[node].r=r;
    if(l==r){
        tree[node].mx=wt[seq[l]];
        return ;
    }
    ll mid=l+r>>1;
    buildtree(node<<1,l,mid);
    buildtree(node<<1|1,mid+1,r);
    pushup(node);
}
inline void modify(ll node,ll x,ll k){
    if(tree[node].l==tree[node].r){
        tree[node].mx=k;
        return ;
    }
    ll mid=tree[node].l+tree[node].r>>1;
    if(x<=mid) modify(node<<1,x,k);
    if(x>mid) modify(node<<1|1,x,k);
    pushup(node);
}
inline ll queryMx(ll node,ll L,ll R){
    if(tree[node].l>=L&&tree[node].r<=R) return tree[node].mx;
    ll mid=tree[node].l+tree[node].r>>1,ans=-1e11;
    if(L<=mid) ans=max(ans,queryMx(node<<1,L,R));
    if(R>mid) ans=max(ans,queryMx(node<<1|1,L,R));
    return ans;
}
inline void update(ll x,ll y){
    modify(1,id[x],y);
}
inline ll queryMaxtree(ll x,ll y){
    if(x==y) return 0;
    ll res=-1e11;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        res=max(res,queryMx(1,id[top[x]],id[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    res=max(res,queryMx(1,id[x]+1,id[y]));
    return res;
}
int main(){
    scanf("%lld",&n);
    for(ll i=1,u,v,w;i<n;i++)
        scanf("%lld%lld%lld",&u,&v,&w),add(u,v,w),add(v,u,w);
    dfs_dep(1,0);
    dfs_new(1,1);
    buildtree(1,1,n);
    while(1){
        string name;
        ll l,r;
        cin>>name;
        if(name=="DONE") break;
        scanf("%lld%lld",&l,&r);
        if(name=="CHANGE"){
            ll pp;
            if(dep[Edge[l].u]>dep[Edge[l].v]) pp=Edge[l].u;
            else pp=Edge[l].v;
            update(pp,r);
        }
        if(name=="QUERY") printf("%lld\n",queryMaxtree(l,r));
    } 
    return 0;
}