仅AC on #1求助

真的调了好久！

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,x,y,sz[N],dep[N],fa[N],w[N],son[N],top[N],tot,rev[N],id[N];
int mx[4*N];
string opt;
vector<pair<int,int> >edge[N];
struct Edge{
    int u,v,w;
}e[N];
void dfs1(int u){
    sz[u]=1;
    for(auto i:edge[u]){
        int v=i.first;
        if(v!=fa[u]){
            w[v]=i.second;
            dep[v]=dep[u]+1;
            fa[v]=u;
            dfs1(v);
            sz[u]+=sz[v];
            if(sz[v]>sz[son[u]]) son[u]=v;
        }
    }
}
void dfs2(int u,int t){
    top[u]=t;
    rev[++tot]=w[u];
    id[u]=tot;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(auto i:edge[u]){
        int v=i.first;
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}
void build(int x,int l,int r){
    if(l==r){
        mx[x]=rev[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*x,l,mid);
    build(2*x+1,mid+1,r);
    mx[x]=max(mx[2*x],mx[2*x+1]);
}
void modify(int x,int l,int r,int h,int v){
    if(l==r){
        mx[x]=v;
        return;
    }
    int mid=(l+r)/2;
    if(h<=mid) modify(2*x,l,mid,h,v);
    else modify(2*x+1,mid+1,r,h,v);
    mx[x]=max(mx[2*x],mx[2*x+1]);
}
int query(int x,int l,int r,int L,int R){
    if(l>=L&&r<=R) return mx[x];
    int mid=(l+r)/2,ret=INT_MIN;
    if(L<=mid) ret=max(ret,query(2*x,l,mid,L,R));
    if(R>mid) ret=max(ret,query(2*x+1,mid+1,r,L,R));
    return ret;
}
void modify_point(int x,int v){
    modify(1,1,n,id[x],v);
}
int query_path(int x,int y){
    int ret=INT_MIN;
    while(dep[top[x]]!=dep[top[y]]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ret=max(ret,query(1,1,n,id[top[x]],id[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    ret=max(ret,query(1,1,n,id[x]+1,id[y]));
    return ret;
}
int main(){
    cin>>n;
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w;
        edge[u].push_back({v,w});
        edge[v].push_back({u,w});
        e[i]={u,v,w};
    }
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    while(1){
        cin>>opt;
        if(opt=="CHANGE"){
            cin>>x>>y;
            x=(dep[e[x].u]>dep[e[x].v])?e[x].u:e[x].v;
            modify_point(x,y);
        }
        else if(opt=="QUERY"){
            cin>>x>>y;
            cout<<query_path(x,y)<<endl;
        }
        else break;
    }
    return 0;
}