记录编号	301335	评测结果	AAAAAAAAAA
题目名称	[SPOJ 375] 难存的情缘	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.851 s
提交时间	2016-08-31 14:00:39	内存使用	13.25 MiB

#include<cstdio>
#include<algorithm>
#include<climits>
//#include"debug.h"
using namespace std;
const int N=200010;
struct edge{int f,t,l;}w[N];
int n,head[N],tail[N],next[N],fa[N],up[N],h[N],size[N],big[N],dfn[N],hash[N],lin[N],cnt;
void add(int f,int num){
	if (!head[f]) head[f]=tail[f]=num;
		else tail[f]=next[tail[f]]=num;
}
void dfs(int x){
	size[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i].t]){
		fa[w[i].t]=x;
		up[w[i].t]=w[i].l;
		h[w[i].t]=h[x]+1;
		dfs(w[i].t);
		size[x]+=size[w[i].t];
		if (size[w[i].t]>size[big[x]]) big[x]=w[i].t;
	}
}
void dfs2(int x){
	hash[dfn[x]=++cnt]=x;
	if (dfn[x]==dfn[fa[x]]+1) lin[x]=lin[fa[x]];
		else lin[x]=x;
	if (!big[x]) return;
	dfs2(big[x]);
	for (int i=head[x];i;i=next[i])
	if (w[i].t!=fa[x]&&w[i].t!=big[x]) dfs2(w[i].t);
}

struct leaf{
	int l,r,Max;
	leaf(int _l=0,int _r=0){l=_l;r=_r;}
}T[N];
void build(int x){
	if (T[x].l==T[x].r){
		T[x].Max=up[hash[T[x].l]];return;
	}
	int mid=(T[x].l+T[x].r)/2;
	T[x*2]=leaf(T[x].l,mid);
	T[x*2+1]=leaf(mid+1,T[x].r);
	build(x*2);build(x*2+1);
	T[x].Max=max(T[x*2].Max,T[x*2+1].Max);
}
void change(int x,int p,int a){
	if (T[x].l>p||T[x].r<p) return;
	if (T[x].l==T[x].r){
		T[x].Max=a;return;
	}
	change(x*2,p,a);change(x*2+1,p,a);
	T[x].Max=max(T[x*2].Max,T[x*2+1].Max);
}
int getmax(int x,int l,int r){
	if (T[x].l>r||T[x].r<l) return INT_MIN;
	if (T[x].l>=l&&T[x].r<=r) return T[x].Max;
	return max(getmax(x*2,l,r),getmax(x*2+1,l,r));
}

int ask(int x,int y){
	int ans=INT_MIN;
	while (lin[x]!=lin[y]){
		if (h[lin[x]]<h[lin[y]]) swap(x,y);
		ans=max(ans,getmax(1,dfn[lin[x]],dfn[x]));
		x=fa[lin[x]];
	}
	if (h[x]<h[y]) swap(x,y);
	ans=max(ans,getmax(1,dfn[y]+1,dfn[x]));
	return ans;
}
int main()
{
	freopen("qtree.in","r",stdin);
	freopen("qtree.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		scanf("%d%d%d",&w[i].f,&w[i].t,&w[i].l);
		w[i+n]=w[i];swap(w[i].f,w[i].t);
		add(w[i].f,i);add(w[i].t,i+n);
	}
	h[1]=fa[1]=1;dfs(1);dfs2(1);
	T[1]=leaf(1,n);build(1);
	char s[10];int x,y;
	while (1){
		scanf("%s",s);
		if (s[0]=='D') break;
		scanf("%d%d",&x,&y);
		if (s[0]=='C'){
			if (w[x].f==fa[w[x].t]) change(1,dfn[w[x].t],y);
				else change(1,dfn[w[x].f],y);
		}
		else printf("%d\n",ask(x,y));
	}
	return 0;
}