记录编号	109014	评测结果	AAAAAAAAAA
题目名称	[SPOJ 375] 难存的情缘	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.174 s
提交时间	2014-07-07 15:49:34	内存使用	0.86 MiB

/*
	Date:2014.7.7
	Author:cstdio
	Algorithm:LCT
	Tips:必须得全加上inline,否则TLE......
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
inline int max(int a,int b,int c){return max(max(a,b),c);}
const int SIZEN=10100,SIZEM=20100;
int N;
class NODE{//伸展树的结点
public:
	int lchild,rchild,father;
	int cost,mx;
	void clear(void){
		lchild=rchild=-1;
		father=0;
		cost=mx=0;
	}
	#define fa(x) tree[x].father
	#define l(x) tree[x].lchild
	#define r(x) tree[x].rchild
	#define cost(x) tree[x].cost
	#define mx(x) tree[x].mx
};
NODE tree[SIZEN];
inline bool isroot(int x){return l(fa(x))!=x&&r(fa(x))!=x;}
inline void update(int x){mx(x)=max(mx(l(x)),mx(r(x)),cost(x));}
inline void print(int x){//调试接口,输出x的信息
	cout<<x<<": "<<endl;
	cout<<"fa:"<<fa(x)<<" l:"<<l(x)<<" r:"<<r(x)<<endl;
	cout<<"cost:"<<cost(x)<<" mx:"<<mx(x)<<endl;cout<<endl;
}
inline void zag(int x){//左旋
	int y=fa(x),z=fa(y);
	if(r(z)==y) r(z)=x;else if(l(z)==y) l(z)=x;
	fa(x)=z,fa(y)=x;
	fa(l(x))=y,r(y)=l(x),l(x)=y;
	update(y);
}
inline void zig(int x){//右旋
	int y=fa(x),z=fa(y);
	if(r(z)==y) r(z)=x;else if(l(z)==y) l(z)=x;
	fa(x)=z,fa(y)=x;
	fa(r(x))=y,l(y)=r(x),r(x)=y;
	update(y);
}
inline void splay(int x){//把x旋转到所在splay的根
	int y,z;
	while(!isroot(x)){
		y=fa(x),z=fa(y);
		if(isroot(y)) l(y)==x?zig(x):zag(x);
		else{
			if(l(z)==y){
				l(y)==x?zig(y):zag(x);
				zig(x);
			}
			else{
				r(y)==x?zag(y):zig(x);
				zag(x);
			}
		}
	}
	update(x);
}
inline void changeval(int x,int t){//把点x的父亲边权值改成t
	cost(x)=t;
	splay(x);
}
inline int access(int x){//访问从x到根的路径
	//如果某条y到根的路径刚被access过那么返回对应的最长边
	int y=-1,ans=0;
	while(x){
		splay(x);
		if(!fa(x)) ans=max(mx(r(x)),mx(y));
		r(x)=y,update(x),y=x;
		x=fa(x);
	}
	return ans;
}
inline int query(int x,int y){//x~y的最长边
	access(y);
	return access(x);
}
class EDGE{
public:
	int to,len;
	int id;
};
int to[SIZEM]={0},len[SIZEM]={0},head[SIZEM]={0},next[SIZEM]={0};
int etot=0;
int lis[SIZEN]={0};//每条边是谁的
inline void answer(void){//回答询问
	char cmd[20]={0};
	int a,b;
	while(true){
		scanf("%s",cmd);
		if(cmd[0]=='D') return;
		else if(cmd[0]=='C'){
			scanf("%d%d",&a,&b);
			changeval(lis[a],b);
		}
		else if(cmd[0]=='Q'){
			scanf("%d%d",&a,&b);
			printf("%d\n",query(a,b));
		}
	}
}
queue<int> Q;
bool vis[SIZEN]={0};
inline void BFS(void){
	while(!Q.empty()) Q.pop();
	memset(vis,0,sizeof(vis));
	Q.push(1);
	vis[1]=true;
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		l(x)=r(x)=-1;
		for(int i=head[x];i;i=next[i]){
			int u=to[i];
			if(vis[u]) continue;
			vis[u]=true;
			fa(u)=x;
			cost(u)=mx(u)=len[i];
			lis[(i+1)/2]=u;
			Q.push(u);
		}
	}
}
inline void addedge(int a,int b,int c){
	to[++etot]=b,len[etot]=c,next[etot]=head[a],head[a]=etot;
}
inline void read(void){
	scanf("%d",&N);
	memset(head,0,sizeof(head));
	memset(next,0,sizeof(next));
	etot=0;
	for(int i=0;i<=N;i++) tree[i].clear();
	int a,b,L;
	for(int i=1;i<N;i++){
		scanf("%d%d%d",&a,&b,&L);
		addedge(a,b,L);
		addedge(b,a,L);
	}
}
int main(){
	freopen("qtree.in","r",stdin);
	freopen("qtree.out","w",stdout);
	read();
	BFS();
	answer();
	/*int T;
	scanf("%d",&T);
	while(T--){
		read();
		BFS();
		answer();
	}*/
	return 0;
}