原题链接

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+5;

int n;
int a[N];
vector<pair<int,int>> G[N];
int fa[N],dep[N],siz[N],son[N],vv[N];
int top[N],dfn[N],seq[N],tim;
struct edge{
	int u,v;
}e[N];

void dfs1(int u,int f)
{
	fa[u]=f;
	dep[u]=dep[f]+1;
	siz[u]=1;
	son[u]=top[u]=0;
	for(auto [v,w]:G[u])
	{
		if(v==f)
			continue;
		vv[v]=w;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])
			son[u]=v;
	}
	return ;
}

void dfs2(int u,int t)
{
//cout<<u<<' '<<son[u]<<'\n';
	dfn[u]=++tim;
	seq[tim]=u;
	top[u]=t;
	if(son[u]==0)
		return ;
	dfs2(son[u],t);
	for(auto [v,w]:G[u])
	{
		if(v==fa[u]||v==son[u])
			continue;
//cout<<v<<' ';
		dfs2(v,v);
	}
	return ;
}

struct xds{
#define ls ((p)<<1)
#define rs (((p)<<1)|1)
	
	int val[N<<3];
	
	void push_up(int p)
	{val[p]=max(val[ls],val[rs]);}
	
	void build(int p,int l,int r)
	{
		if(l==r)
		{
			val[p]=vv[seq[l]];
			return ;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		return ;
	}
	
	void upd(int p,int l,int r,int x,int k)
	{
		if(l==r)
		{
			val[p]=k;
			return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid)
			upd(ls,l,mid,x,k);
		else
			upd(rs,mid+1,r,x,k);
		push_up(p);
		return ;
	}
	
	int query(int p,int l,int r,int ql,int qr)
	{
//		if(l>r)
//			return 0;
		if(ql<=l&&r<=qr)
			return val[p];
		int mid=(l+r)>>1,res=-1;
		if(ql<=mid)
			res=max(res,query(ls,l,mid,ql,qr));
		if(qr>mid)
			res=max(res,query(rs,mid+1,r,ql,qr));
		return res;
	}
	
	int query_chain(int x,int y)
	{
		if(x==y)
			return 0;
		int res=0;
		while(top[x]!=top[y])
		{
			if(dep[top[x]]<dep[top[y]])
				swap(x,y);

//cout<<top[x]<<' '<<x<<':';
//cout<<query(1,1,n,dfn[top[x]],dfn[x])<<'\n';

//cout<<query(1,1,n,dfn[top[x]],dfn[x])<<'|';

			res=max(res,query(1,1,n,dfn[top[x]],dfn[x]));
			x=fa[top[x]];
		}
		if(dep[x]>dep[y])
			swap(x,y);
		
//cout<<x<<' '<<y<<':';
//cout<<query(1,1,n,dfn[x]+1,dfn[y])<<'\n';

//cout<<query(1,1,n,dfn[x]+1,dfn[y])<<'\n';
		
		return max(res,query(1,1,n,dfn[x]+1,dfn[y]));
	}
}t;

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[i].u=u,e[i].v=v;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
		a[i+1]=w;
	}
	
	dfs1(1,0);
//cout<<"&\n";
	
//for(int i=1;i<=n;i++)
//	cout<<son[i]<<' ';
	
	dfs2(1,1);
//cout<<"&&\n";
	t.build(1,1,n);
//cout<<"&&&";

//for(int i=1;i<=n;i++)
//	cout<<i<<':'<<t.query(1,1,n,dfn[i],dfn[i])<<'|';
//cout<<'\n';
	
	while(1)
	{
		string s;
		cin>>s;
		if(s=="CHANGE")
		{
			int x,k;
			cin>>x>>k;
			int u=e[x].u,v=e[x].v;
			if(dep[u]<dep[v])
				swap(u,v);
			t.upd(1,1,n,dfn[u],k);
		}
		else if(s=="QUERY")
		{
			int a,b;
			cin>>a>>b;
			cout<<t.query_chain(a,b)<<'\n';
		}
		else
			break;
		
//for(int i=1;i<=n;i++)
//	cout<<i<<':'<<t.query(1,1,n,dfn[i],dfn[i])<<'|';
//cout<<'\n';
	}
	
	return 0;
}