用重链剖分做的

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
namespace akioi{
	const int N=3e5+10;
	const int INF=0x3f3f3f3f;
	int n;
	int h[N],ne[2*N],e[2*N],w[2*N],o[2*N],idx;
	int sz[N],maxx[N],g[N];
	int dfn[N],idx_dfn,sa[N];
	int top[N],dep[N],fa[N],hei[N];
	int Root,a[N],yjf[N];
	struct node{
		int maxx;
	}tree[4*N];

	void up(int k){
		tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
	}

	void build(int k,int l,int r){
		if(l==r){
			tree[k].maxx=dfn[l];
			return ;
		}
		int mid=(l+r)>>1;
		build(2*k,l,mid);
		build(2*k+1,mid+1,r);
		up(k);
	}

	int query(int k,int l,int r,int L,int R){
		if(r<L || R<l) return 0;
		if(L<=l && r<=R){
			return tree[k].maxx;
		}
		int mid=(l+r)>>1;
		return max(query(2*k,l,mid,L,R),query(2*k+1,mid+1,r,L,R));
	}

	void modify(int k,int l,int r,int L,int d){
		if(r<L || L<l) return ;
		if(l==r){
			tree[k].maxx=d;
			return ;
		}
		int mid=(l+r)>>1;
		modify(2*k,l,mid,L,d);
		modify(2*k+1,mid+1,r,L,d);
		up(k);
	}

	void add(int x,int y,int z,int k){
		e[++idx]=y;
		w[idx]=z;
		o[idx]=k;
		ne[idx]=h[x];
		h[x]=idx;
	}

	void dfs1(int u,int de,int last){
		yjf[u]=last;
		sz[u]=1;
		for(int i=h[u];i!=-1;i=ne[i]){
			if(last==o[i]) continue;
			dep[o[i]]=de;
			dfs1(e[i],de+1,o[i]);
			sz[u]+=sz[e[i]];
			fa[o[i]]=last;
			if(sz[e[i]]>=maxx[u]){
				maxx[u]=sz[e[i]];
				g[u]=i;
			}
		}
	}

	void dfs2(int u,int tp,int last){
//		cout<<u<<' '<<last<<'\n';


		if(g[u]!=0){
			dfn[++idx_dfn]=w[g[u]];
			sa[o[g[u]]]=idx_dfn;
			top[o[g[u]]]=tp;
			dfs2(e[g[u]],tp,o[g[u]]);
		}
		for(int i=h[u];i!=-1;i=ne[i]){
			if(o[i]!=last && i!=g[u]){
				dfn[++idx_dfn]=w[i];
				top[o[i]]=o[i];
				sa[o[i]]=idx_dfn;
				dfs2(e[i],o[i],o[i]);
			}
		}
	}

	int query_lca(int x,int y){
		int ans=0;
		while(top[x]!=top[y]){
//			cout<<"!!!";
			if(dep[top[x]]>dep[top[y]]){
				ans=max(query(1,1,n,sa[top[x]],sa[x]),ans);
//				cout<<"DDD"<<sa[top[x]]<<' '<<sa[x]<<'\n';
				x=fa[top[x]];
			}
			else{
				ans=max(query(1,1,n,sa[top[y]],sa[y]),ans);
//				cout<<"DDD"<<sa[top[y]]<<' '<<sa[y]<<'\n';
				y=fa[top[y]];
			}
		}
		if(dep[x]>dep[y]){
			ans=max(ans,query(1,1,n,sa[y]+1,sa[x]));
//			cout<<sa[y]+1<<' '<<sa[x]<<'\n';
		}
		else{
			ans=max(ans,query(1,1,n,sa[x]+1,sa[y]));
//			cout<<x<<' '<<y<<' '<<sa[x]+1<<' '<<sa[y]<<'\n';
		}
		return ans;
	}

	int main(){
		memset(h,-1,sizeof(h));
		scanf("%d",&n);
		int x,y,z;
		for(int i=1;i<n;i++){
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z,i);
			add(y,x,z,i);
//			if(z==0) return 0;
		}
		dfn[++idx_dfn]=0;
		sa[0]=1;
		dfs1(1,1,0);
//		cout<<"!!!";
		dfs2(1,1,0);
		build(1,1,n);
//        for(int i=1;i<=n;i++){
//			cout<<fa[i]<<'\n';
//		}
		char op[10];
		for(int i=1;i;i++){
			scanf("%s",op);
			if(op[0]=='C'){
				cin>>x>>y;
				modify(1,1,n,sa[x],y);
			}
			else if(op[0]=='Q'){
				cin>>x>>y;
				if(x==y) printf("0\n");
				else{
//					cout<<yjf[x]<<' '<<yjf[y]<<'\n';
					int tmp=query_lca(yjf[x],yjf[y]);
					printf("%d\n",tmp);
				}
			}
			else{
				break;
			}
		}
		return 0;
	}
}
signed main(){
	return akioi::main();
}
/*
5 1
1 2 1
2 3 100
3 4 2
1 5 3
1 5 2
*/