https://www.luogu.com.cn/record/135397522

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n;
int deg[N],maxlen[N],maxlenson[N],id[N],v[N],ftop[N],faa[N],fid[N];
int ind,cnt;
vector<int> ma[N];

void dfs(int u,int fa)
{
	faa[u]=fa;
	deg[u]=deg[fa]+1;
	for(int i=0;i<ma[u].size();i++)
	{
		if(ma[u][i]==fa) continue;
		dfs(ma[u][i],u);
		if(maxlen[u]<maxlen[ma[u][i]])
		{
			maxlen[u]=maxlen[ma[u][i]];
			maxlenson[u]=ma[u][i];
		}
	}
	maxlen[u]++;
}

void dfs2(int u,int fa)
{
	id[u]=++ind;
	fid[ind]=u;
	if(maxlenson[u])
	{
		ftop[maxlenson[u]]=ftop[u];
		dfs2(maxlenson[u],u);
	}
	for(int i=0;i<ma[u].size();i++)
	{
		if(ma[u][i]==fa||ma[u][i]==maxlenson[u]) continue;
		ftop[ma[u][i]]=ma[u][i];
		dfs2(ma[u][i],u);
	}
}

class segment_tree{
public:
	struct tree{
		int l,r,maxx;
		void clear(){ l=r=maxx=0;}
	};
	
	vector<tree> tr;
	
	segment_tree(int l,int r){
		tree temp;
		temp.clear();
		tr.resize(N*4,temp);
		build(1,l,r);
	}
	
	void pushup(int k){tr[k].maxx=max(tr[k<<1].maxx,tr[k<<1|1].maxx);}
	
	void build(int k,int l,int r)
	{
		tr[k].l=l,tr[k].r=r;
		if(l==r) return void(tr[k].maxx=v[fid[l]]);
		int mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		pushup(k);
	}
		
	void change(int k,int pos,int index)
	{
		if(tr[k].l==tr[k].r) return void(tr[k].maxx=pos);
		int mid=(tr[k].l+tr[k].r)>>1;
		if(index<=mid) change(k<<1,pos,index);
		else if(mid<index) change(k<<1|1,pos,index);
		pushup(k);
	} 
	
	int query(int k,int l,int r)
	{
		if(l<=tr[k].l&&tr[k].r<=r) return tr[k].maxx;
		int mid=(tr[k].l+tr[k].r)>>1,res=0;
		if(l<=mid) res=max(res,query(k<<1,l,r));
		if(mid<r) res=max(res,query(k<<1|1,l,r));
		return res;
	}
};
signed main()
{
	cin >> n;
//	for(int i=1;i<=n;i++) v[i]=-2e9;
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		cin >> x >> y >> z;
		v[n+i]=z;
		ma[x].push_back(n+i);
		ma[y].push_back(n+i);
		ma[n+i].push_back(x);
		ma[n+i].push_back(y);
	}
	ftop[1]=1;
	dfs(1,0);
	dfs2(1,0);
	segment_tree tree(1,n+n-1);
//	for(int i=1;i<=n+n-1;i++) printf("%d ",id[i]); 
//	printf("\n");
//	for(int i=1;i<=n+n-1;i++) printf("%d ",fid[i]);  
//	printf("\n");
//	build(1,1,ind);
	
	while(1)
	{
		string opt;
		cin >> opt;
		if(opt=="DONE") break;
		int x,y;
		cin >> x >> y;
		if(opt=="QUERY")
		{
			int res=0;
			while(ftop[x]!=ftop[y])
			{
				if(deg[x]<deg[y]) swap(x,y);
				res=max(tree.query(1,id[ftop[x]],id[x]),res);
				x=faa[ftop[x]];
//				cout << x << ' ' << y << '\n'; 
			}
			if(deg[x]<deg[y]) swap(x,y);
 			res=max(tree.query(1,id[y]+1,id[x]),res);
			cout << res << '\n';
		}
		else tree.change(1,y,id[x+n]);
	}
	return 0;
}
/*
4
1 2 1
2 3 2
1 4 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
*/