蒟蒻+萌新求助

只有70分QAQ

#include<iostream>
#include<cstdio>
using namespace std;

const int M=3e5+5;

int n,cnt=0,a[M],de[M],fa[M],son[M],top[M],num[M],pre[M],size[M];
int tot=0,first[M];
struct Edge{
    int nxt,to,val;
}e[M<<1];
struct Tree{
    int maxn;
}tr[M<<2];
struct CuCun{
    int x,y,z;
}c[M];

int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') y=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*y;
}

void add(int x,int y,int z){
    tot++;
    e[tot].nxt=first[x];
    first[x]=tot;
    e[tot].to=y;
    e[tot].val=z;
}

void dfs1(int u,int f){
    fa[u]=f;
    de[u]=de[f]+1;
    size[u]=1;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].val;
        if(v==f) continue;
        a[v]=w;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[son[u]]<size[v]) son[u]=v;
    }
}

void dfs2(int u,int tp){
    num[u]=++cnt;
    pre[cnt]=u;
    top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

void pushup(int u){
    tr[u].maxn=max(tr[u<<1].maxn,tr[u<<1|1].maxn);
}

void build(int u,int l,int r){
    if(l==r){
        tr[u].maxn=a[pre[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void change(int u,int l,int r,int x,int d){
    if(l==r&&l==x){
        tr[u].maxn=d;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid) change(u<<1,l,mid,x,d);
    else change(u<<1|1,mid+1,r,x,d);
    pushup(u);
}

int query_max(int u,int l,int r,int L,int R){
    if(L>r||R<l) return -1<<30;
    if(L<=l&&R>=r) return tr[u].maxn;
    int mid=(l+r)>>1;
    return max(query_max(u<<1,l,mid,L,R),query_max(u<<1|1,mid+1,r,L,R));
}

int qmax(int x,int y){
    int ans=-1<<30;
    while(top[x]!=top[y]){
        if(de[top[x]]<de[top[y]]) swap(x,y);
        ans=max(ans,query_max(1,1,n,num[top[x]],num[x]));
        x=fa[top[x]];
    }
    if(de[x]<de[y]) swap(x,y);
    ans=max(ans,query_max(1,1,n,num[y]+1,num[x]));
    return ans;
}

int main(){
    n=read();
    for(int i=1;i<=n-1;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
        c[i].x=x,c[i].y=y,c[i].z=z;
    }
    a[1]=-1<<30;
    dfs1(1,1);
    dfs2(1,1);
    build(1,1,n);
//  for(int i=1;i<=n;i++) printf("%d ",a[pre[i]]);
//    printf("\n");
    char s[15];
    while(1){
        scanf("%s",s);
        if(s[0]=='D') break;
        int x=read(),y=read();
        if(s[0]=='Q') printf("%d\n",qmax(x,y));
        if(s[0]=='C'){
            int u=c[x].x,v=c[x].y;
            if(fa[v]==u) swap(u,v);
            change(1,1,n,num[u],y);
        }
    }
}