就是标准的用线段树维护树链剖分。

#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
long long read(){
	long long x=0,sgn=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')sgn=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	return x*sgn;
}
void write(long long n){
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10+'0');
}
long long n,a[maxn],x,y,z;
long long kk,poi[maxn],nex[maxn],v[maxn],w[maxn];
long long f[maxn],dis[maxn],siz[maxn],h[maxn];
long long top[maxn],dfn[maxn],rnk[maxn],cnt;
struct edge{
	long long x,y;
}e[maxn];
struct node{
	long long l,r,ma;
}t[4*maxn];
char st[20];
long long k,ans;
void add_edge(long long x,long long y,long long z){
	kk++;v[kk]=y;w[kk]=z;nex[kk]=poi[x];poi[x]=kk;
}
void dfs1(long long x,long long fa){
	long long save=poi[x];
	siz[x]=1;
	while(save>0){
		if(v[save]!=fa){
			f[v[save]]=x;
			a[v[save]]=w[save];
			dis[v[save]]=dis[x]+1;
			dfs1(v[save],x);
			siz[x]+=siz[v[save]];
		}
		save=nex[save];
	}
	save=poi[x];
	while(save>0){
		if(v[save]!=fa)
			if(a[v[save]]>a[h[x]])h[x]=v[save];
		save=nex[save];
	}
}
void dfs2(long long x,long long ding){
	cnt++;dfn[x]=cnt;rnk[cnt]=x;top[x]=ding;
	if(h[x]!=0)dfs2(h[x],ding);
	long long save=poi[x];
	while(save>0){
		if(v[save]!=f[x]&&v[save]!=h[x])
			dfs2(v[save],v[save]);
		save=nex[save];
	}
}
void build(long long i,long long l,long long r){
	t[i].l=l;t[i].r=r;
	if(l==r){
		t[i].ma=a[rnk[l]];
		return;
	}
	long long mid=(l+r)>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	t[i].ma=max(t[i*2].ma,t[i*2+1].ma);
}
void chaxun(long long i,long long x,long long y){
	if(x<=t[i].r&&y>=t[i].l){
		if(x<=t[i].l&&y>=t[i].r){
			ans=max(ans,t[i].ma);
			return;
		}
		chaxun(i*2,x,y);
		chaxun(i*2+1,x,y);
	}
}
void xiugai2(long long i,long long x,long long y,long long k){
	if(x<=t[i].r&&y>=t[i].l){
		if(x<=t[i].l&&y>=t[i].r){
			//直接覆
			t[i].ma=k; 
			return; 
		}
		xiugai2(i*2,x,y,k);
		xiugai2(i*2+1,x,y,k);
		t[i].ma=max(t[i*2].ma,t[i*2+1].ma);
	}
}

int main(){
//	long long t=clock();
//	freopen("1.in","r",stdin);	
//	freopen("114.out","w",stdout); 
	n=read();
	for(int i=1;i<=n-1;i++){
		x=read();y=read();z=read();
		e[i].x=x;e[i].y=y;
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	
	dis[1]=1;
	dfs1(1,0);
	dfs2(1,1);
	//线段树中存储的是重新编号之后的编号 
	build(1,1,n);
	while(1){
		scanf("%s",st);
		ans=0;
		if(st[0]=='D')break;
		if(st[0]=='Q'){
			x=read();y=read();
			if(x==y){
				write(0);putchar('\n');
				continue;
			}
			while(top[x]!=top[y]){
				if(dis[top[x]]<dis[top[y]])swap(x,y);
				chaxun(1,dfn[top[x]],dfn[x]);
				x=f[top[x]];
				//cout<<x<<" "<<y<<endl;
			}
			if(dis[x]>dis[y])swap(x,y);
			chaxun(1,dfn[x]+1,dfn[y]);
			write(ans);putchar('\n');
		}
		if(st[0]=='C'){
			x=read();k=read();
			if(dis[e[x].x]>dis[e[x].y])x=e[x].x;
			else x=e[x].y;
			xiugai2(1,dfn[x],dfn[x],k);
		}
	}
	return 0;
}

快读快输什么都加上了，但还是T。我觉得复杂度没有问题啊。