树剖全部MLE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100050;
int n;
struct node{
    int to,next,value;
}edge[N<<1];
int head[N],tot,val[N],cnt,id[N],tr[N<<2],tag[N<<2];
int top[N],siz[N],fa[N],son[N],dep[N],rid[N];

void add(int x,int y,int v){
    tot++;
    edge[tot].to=y;
    edge[tot].value=v;
    edge[tot].next=head[x];
    head[x]=tot;
}
void dfs1(int x){
    siz[x]=1;
    dep[x]=dep[fa[x]]++;
    for(int i=head[x];i!=0;i=edge[i].next){
        int xx=edge[i].to;
        if(xx==fa[x]) continue;
        fa[xx]=x;
        dfs1(xx);
        siz[x]+=siz[xx];
        val[xx]=edge[i].value;
        if(!son[x] || siz[xx]>siz[son[x]]){
            son[x]=xx;
        }
    }
}
void dfs2(int x,int tv){
    top[x]=tv;
    cnt++;
    id[x]=cnt;
    rid[cnt]=val[x];
    if(son[x]) dfs2(son[x],tv);
    for(int i=head[x];i!=0;i=edge[i].next){
        int xx=edge[i].to;
        if(xx==son[x] || xx==fa[x]) continue;
        dfs2(xx,xx);
    }
}
void pushup(int root){
    tr[root]=max(tr[root<<1],tr[root<<1|1]);
}

void build(int root,int start,int end){
    if(start==end){
        tr[root]=rid[start];
        return ; 
    }
    int mid=(start+end)>>1;
    build(root<<1,start,mid);
    build(root<<1|1,mid+1,end);
    pushup(root);
}
void updata(int root,int start,int end,int loc,int val){
    if(start==end){
        tr[loc]=val;
        return ;
    }
    int mid=(start+end)>>1;
    if(loc<=mid) updata(root<<1,start,mid,loc,val);
    else updata(root<<1|1,mid+1,end,loc,val);
    pushup(root);
}
int qurey(int root,int start,int end,int l,int r){
    cout<<start<<" "<<end<<" "<<l<<" "<<r<<endl;
    if(start>=l && end<=r) return tr[root];
    int mid=(start+end)>>1,res=0;
    if(mid>=l) res=max(res,qurey(root<<1,start,mid,l,r));
    if(mid<r) res=max(res,qurey(root<<1|1,mid+1,end,l,r));
    return res;
}
int shup(int x,int y){
    int res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        res=max(res,qurey(1,1,n,id[top[x]],id[x]));
        x=fa[top[x]];
        cout<<"1"<<endl;
    }
    if(dep[x]>dep[y]) swap(x,y);
    res=max(res,qurey(1,1,n,id[y]+1,id[x]));
    cout<<"1"<<endl;
    return res;
}
signed main(){
    //freopen("P4114_1.in","r",stdin);
    //freopen("P4114_1.out","w",stdout); 
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z),add(y,x,z);
    }
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    string w;
    while(cin>>w){
        if(w[0]=='D') break;
        else if(w[0]=='Q'){
            int x,y;
            cin>>x>>y;
            if(x==y) cout<<"0"<<endl;
            else cout<<shup(x,y)<<endl;
        }
        else{
            int x,y;
            cin>>x>>y;
            updata(1,1,n,x,y);
        }
    }
    return 0;
}