为什么会MLE

萌新求助 RT

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
#define mid ((l+r)>>1)
#define ls rt<<1
#define rs rt<<1|1
const int maxn=1e5+6;
template<class T>inline void read(T &x) {
    T f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+(s&15);s=getchar();}
    x*=f;
}
template<class T>inline T min(T a,T b) { return a<b?a:b; }
template<class T>inline T max(T a,T b) { return a>b?a:b; }
struct Edge {
    int u,v,w,id;
}e[maxn<<1];
int head[maxn],cnt;
inline void addedge(int u,int v,int w,int id) { e[++cnt].v=v;e[cnt].w=w;e[cnt].u=head[u];head[u]=cnt; }
inline void add(int u,int v,int w,int id) { addedge(u,v,w,id); addedge(v,u,w,id); }
int val[maxn<<2];
inline void pushup(int rt) { val[rt]=max(val[ls],val[rs]); }
inline void insert(int rt,int l,int r,int k,int ch) {
    if(l==r) return (void)(val[rt]=ch);
    if(k<=mid) insert(ls,l,mid,k,ch);
    else insert(rs,mid+1,r,k,ch);
    pushup(rt);
}
inline int query(int rt,int l,int r,int L,int R) {
    int ans=0;
    if(L<=l&&r<=R) return val[rt];
    if(L<=mid) ans=max(ans,query(ls,l,mid,L,R));
    if(R>mid) ans=max(ans,query(rs,mid+1,r,L,R));
    return ans;
}
int dep[maxn],top[maxn],siz[maxn],son[maxn],fa[maxn],id[maxn],n,tot,now[maxn];
inline void dfs1(int x,int f,int d) {
    dep[x]=d; fa[x]=f; siz[x]=1;
    for(int i=head[x];i;i=e[i].u) {
        if(e[i].v==f) continue;
        dfs1(e[i].v,x,d+1);
        siz[x]+=siz[e[i].v];
        if(siz[e[i].v]>siz[son[x]]) son[x]=e[i].v;
    }
}
inline void dfs2(int x,int topf) {
    top[x]=topf;
    if(!son[x]) return;
    for(int i=head[x];i;i=e[i].u) {
        if(e[i].v==fa[x]) continue;
        id[e[i].v]=++tot;
        now[e[i].id]=tot;
        insert(1,1,n,id[e[i].v],e[i].w);
        if(e[i].v==son[x]) dfs2(son[x],topf);
        else dfs2(e[i].v,e[i].v);
    }
}
inline int qRange(int x,int y) {
    int ans=0;
    while(top[x]!=top[y]) {
        if(dep[top[x]]>dep[top[y]]) {
            ans=max(ans,query(1,1,n,id[top[x]]+1,id[x]));
            x=fa[top[x]];
        }
        else {
            ans=max(ans,query(1,1,n,id[top[y]]+1,id[y]));
            y=fa[top[y]];
        }
    }
    if(dep[x]>dep[y]) ans=max(ans,query(1,1,n,id[y]+1,id[x]));
    else ans=max(ans,query(1,1,n,id[x]+1,id[y]));
    return ans;
}
char s[10];
int a,b,c,x,y;
int main() {
    read(n);
    for(int i=1;i<n;i++) read(a),read(b),read(c),add(a,b,c,i);
    dfs1(1,0,1);dfs2(1,1);
    while(1) {
        scanf("%s",&s);
        if(s[0]=='D') break;
        read(x); read(y);
        if(s[0]=='C') {
            insert(1,1,n,now[x],y);
        }
        else {
            printf("%d\n",qRange(x,y));
        }
    }
}