帮帮孩子吧/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);
		}
	}
}