记录编号	538720	评测结果	AAAAAAAAAA
题目名称	[SPOJ 375] 难存的情缘	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.402 s
提交时间	2019-07-30 11:09:10	内存使用	14.86 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 1e9
const int maxn=15000;
struct Edge{
	int from,to,next,dis;
}e[maxn<<1];
int len,head[maxn];
void Insert(int x,int y,int z){
	len++;e[len].from=x;e[len].to=y;e[len].next=head[x];e[len].dis=z;head[x]=len;
}
int n; 
int deep[maxn],size[maxn],root[maxn],son[maxn],v[maxn];
void Dfs1(int x){
	size[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(root[x]!=j){
			root[j]=x;
			deep[j]=deep[x]+1;
			v[j]=e[i].dis;
			Dfs1(j);
			size[x]+=size[j];
			if(size[son[x]]<size[j]) son[x]=j;
		}
	}
}
int id[maxn],pos[maxn],cnt,top[maxn];
void Dfs2(int x,int tp){
	id[x]=++cnt;pos[cnt]=x;top[x]=tp;
	if(son[x]) Dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(root[x]!=j && son[x]!=j) Dfs2(j,j);
	}
}
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int Max[maxn<<2];
void Build(int rt,int l,int r){
	if(l==r){
		Max[rt]=v[pos[l]];
		return;
	}
	int mid=(l+r)>>1;
	Build(lson);Build(rson);
	Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
int Query_Max(int s,int t,int rt,int l,int r){
	if(s<=l && t>=r) return Max[rt];
	int mid=(l+r)>>1;
	if(t<=mid) return Query_Max(s,t,lson);
	if(s>mid) return Query_Max(s,t,rson);
	return max(Query_Max(s,t,lson),Query_Max(s,t,rson));
}
int Tree_Max(int x,int y){
	int ans=-Inf,fx=top[x],fy=top[y];
	while(fx^fy){
		if(deep[fx]<deep[fy]) swap(x,y),swap(fx,fy);
		ans=max(ans,Query_Max(id[fx],id[x],1,1,n));
		x=root[fx];fx=top[x];
	}
	if(deep[x]>deep[y]) swap(x,y);
	if(id[x]+1<=id[y]) ans=max(ans,Query_Max(id[x]+1,id[y],1,1,n));
	return ans; 
}
void Change(int x,int z,int rt,int l,int r){
	if(l==r) {
		Max[rt]=z;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) Change(x,z,lson);
	else Change(x,z,rson);
	Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
void Init();
int main(){
	freopen("qtree.in","r",stdin);
	freopen("qtree.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z);Insert(y,x,z);
	}
	Dfs1(1);
	Dfs2(1,1); 
	Build(1,1,n);
	char s[10];
	while(scanf("%s",s+1) && s[1]!='D'){
		int x,y;scanf("%d%d",&x,&y);
		if(s[1]=='Q') printf("%d\n",Tree_Max(x,y));
		else {
			int fr=e[x<<1].from,to=e[x<<1].to;
			if(root[fr]==to) Change(id[fr],y,1,1,n);
			else Change(id[to],y,1,1,n);
		}
	}
}