记录编号	302642	评测结果	EEEEEEEEEE
题目名称	延绵的山峰	最终得分	0
用户昵称	浮生随想	是否通过	未通过
代码语言	C++	运行时间	1.380 s
提交时间	2016-09-04 15:20:21	内存使用	67.39 MiB

#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cstring>
#define lch rt<<1,l,mid
#define rch rt<<1|1,mid+1,r
#define mid ((l+r)>>1)
using namespace std;
const int maxn=1000010;
struct edge{
	int to,next,dis,id;
}a[maxn<<1];
int len=0,head[maxn],b[maxn<<2],n,tem,size[maxn],son[maxn],fa[maxn],id[maxn],deep[maxn];
int top[maxn],pos[maxn],val[maxn],t[maxn],cnt=0;
void insert(int u,int v,int w,int h){
	len++;a[len].to=v;a[len].dis=w;a[len].next=head[u];a[len].id=h;head[u]=len;
}
void dfs1(int x){
	son[x]=0;size[x]=1;
	for(int i=head[x];i;i=a[i].next){
		int to=a[i].to;
		if(to!=fa[x]){
			val[to]=a[i].dis;
			t[a[i].id]=to;
			deep[to]=deep[x]+1;
			fa[to]=x;
			dfs1(to);
			size[x]+=size[to];
			if(size[to]>size[son[x]])son[x]=to;
		}
	}
}
void dfs2(int x,int t){
	top[x]=t;id[x]=++cnt;pos[cnt]=x;
	if(son[x]) dfs2(son[x],t);
	for(int i=head[x];i;i=a[i].next){
		int to=a[i].to;
		if(!top[to])	dfs2(to,to);
	}
}
void build(int rt,int l,int r){
	if(l==r){
		b[rt]=val[pos[l]];
		return;
	}
	build(lch);
	build(rch);
	b[rt]=max(b[rt<<1],b[rt<<1|1]);
}
int query(int s,int t,int rt,int l,int r){
	int ans=0;
	if(s<=l&&t>=r){
		return b[rt];
	}
	if(s<=mid) ans=max(ans,query(s,t,lch));
	if(t>mid) ans=max(ans,query(s,t,rch));
	return ans;
}
/*int query(int s,int t,int rt,int l,int r){
	if(s<=l&&t>=r){
		return b[rt];
	}
	if(s>mid)return query(s,t,rch);
	if(t<=mid)return query(s,t,lch);
	return max(query(s,t,lch),query(s,t,rch));
}*/
void change(int x,int y,int rt,int l,int r)
{
	if(l==r&&l==x){
		b[rt]=y;
		return;
	}
	if(x<=mid) change(x,y,lch);
	else change(x,y,rch);
	b[rt]=max(b[rt<<1],b[rt<<1|1]);
}
int anss(int x,int y){
	int ans=-0x7f7f7f7f;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		ans=max(ans,query(id[top[x]],id[x],1,1,n));
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	ans=max(ans,query(id[son[x]],id[y],1,1,n));
	return ans;	
}
 
int main(){
	freopen("qtree.in","r",stdin);
	freopen("qtree.out","w",stdout);
	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,i);
		insert(y,x,z,i);
	} 
	deep[1]=1;
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	for(;;){
		string s;
		cin>>s;
		if(s[0]=='D')break;
		int x,y;
		scanf("%d%d",&x,&y);
		if(s[0]=='Q')
		printf("%d\n",anss(x,y));
		else
			change(id[t[x]],y,1,1,n);
	}
	//system("pause");
}