树剖炸了

帮帮孩子吧/kk

#include <bits/stdc++.h>
using namespace std;
int depth[200005],size[200005],son[200005],fa[200005],top[200005],rk[200005],tot,di[200005],din[200005];
struct Edge{
    int u,v,w;
}qvq[200005];
vector<Edge> edge[200005];
struct tree{
    int to,laz;
}tr[800005];
int p,ansx,n,m,R;
void pushup(int u){
    tr[u].to=max(tr[u*2].to,tr[u*2+1].to);
}
void build(int l,int r,int u){
    if (l==r){
        tr[u].to=din[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,u*2);
    build(mid+1,r,u*2+1);
    pushup(u);
    return ;
}
void update(int l,int r,int L,int R,long long la,int u){
    if (l>=L&&r<=R){
        tr[u].to=la;
        return ;
    }
//  pushdown(l,r,u);
    int mid=(l+r)/2;
    if (mid>=L) update(l,mid,L,R,la,u*2);
    if (mid<R) update(mid+1,r,L,R,la,u*2+1);
    pushup(u);
    return ;
}
int getsum(int l,int r,int L,int R,int u){
    if (l>=L&&r<=R) return tr[u].to;
//  pushdown(l,r,u);
    int ans=-1e9;
    int mid=(l+r)/2;
    if (mid>=L) ans=max(getsum(l,mid,L,R,u*2),ans);
    if (mid<R) ans=max(getsum(mid+1,r,L,R,u*2+1),ans);
    return ans;
}
void dfs1(int dep,int now,int fat){
    depth[now]=dep;
    fa[now]=fat;
    size[now]=1;
    int len=edge[now].size();
    int maxx=-1e9;
    for (register int i=0;i<len;i++){
        int qwq=edge[now][i].v;
        if (qwq==fat){
            di[now]=edge[now][i].w;
            continue ;
        }
        dfs1(dep+1,qwq,now);
        size[now]+=size[qwq];
        if (size[qwq]>maxx) maxx=size[qwq],son[now]=qwq;
    }
    return ;
}
void dfs2(int now,int tf){
    rk[now]=++tot;
    top[now]=tf;
    din[tot]=di[now];
    if (!son[now]) return ;
    int len=edge[now].size();
    dfs2(son[now],tf);
    for (register int i=0;i<len;i++){
        int qwq=edge[now][i].v;
        if (qwq==fa[now]||qwq==son[now]) continue ;
        dfs2(qwq,qwq);
    }
    return ;
}
int czmg(int x,int y){
    int ans=-1;
    while(top[x]!=top[y]){
        if (depth[top[x]]<depth[top[y]]) swap(x,y);
        ans=max(ans,getsum(1,n,rk[top[x]],rk[x],1));
        x=fa[top[x]];
    }
    if (depth[x]>depth[y]) swap(x,y);
    ans=max(getsum(1,n,rk[x]+1,rk[y],1),ans);
    return ans;
}
int main(){
//  freopen("qwq.in","r",stdin);
//  freopen("qwq.out","w",stdout);
    cin >> n;
    for (register int i=1;i<=n-1;i++){
        int x,y,z;
        cin >> x >> y >> z;
        edge[x].push_back(Edge{x,y,z});
        edge[y].push_back(Edge{y,x,z});
        qvq[i].u=x,qvq[i].v=y,qvq[i].w=z;
    }
    dfs1(1,1,0);
    dfs2(1,1);
    build(1,n,1);
    for (register int i=1;;i++){
        string qsq;
        cin >> qsq;
        if (qsq=="DONE") return 0;
        if (qsq=="QUERY"){
            int x,y;
            cin >> x >> y;
            if (x==y) cout << 0 << endl;
            else cout << czmg(x,y) << endl;
        }
        if (qsq=="CHANGE"){
            int x,k,sd;
            cin >> x >> k;
            if (depth[qvq[x].u]>depth[qvq[x].v]) sd=qvq[x].u;
            else sd=qvq[x].v;
            update(1,n,sd,sd,k,1);
        }
    }
}