记录编号	323750	评测结果	AAAAAAAAAA
题目名称	[SPOJ 375] 难存的情缘	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.289 s
提交时间	2016-10-17 06:30:42	内存使用	2.61 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
const int maxn = 10010 << 2 ;
int top[maxn],deep[maxn],fa[maxn],dfn[maxn],size[maxn],son[maxn],pos[maxn],id[maxn],dis[maxn];
int head[maxn],tot,cnt,n,m,k,x,y,z,maxnum[maxn],L,R;
struct Edge{
	int to,next,dis,num;
}edge[maxn];
void Addedge(int x,int y,int z,int w){
	edge[++tot].to=y;
	edge[tot].dis=z;
	edge[tot].num=w;
	edge[tot].next=head[x];
	head[x]=tot;
}
void dfs1(int x){
	size[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int p=edge[i].to;
		if(!size[p]){
			deep[p]=deep[x]+1;
			fa[p]=x;
			pos[ edge[i].num ] = p ;
			dis[p] = edge[i].dis;
			dfs1(p);
			size[x] += size[p];
			if(size[son[x]]<size[p])son[x]=p;
		}
	}
}
void dfs2(int x,int tp)
{
	top[x]=tp;dfn[x]=++cnt;id[cnt]=x;
	if(size[son[x]])dfs2(son[x],tp);
	for(int i=head[x];i;i=edge[i].next){
		int p=edge[i].to;
		if(!dfn[p])dfs2(p,p);
	}
}
void Build(int rt,int l,int r)
{
	if(l==r){
		maxnum[rt] = dis[ id[l] ] ;
		return;
	}
	int mid = (l+r)>>1;
	Build(rt<<1,l,mid);
	Build(rt<<1|1,mid+1,r);
	maxnum[rt]=std::max(maxnum[rt<<1],maxnum[rt<<1|1]);
}
int query_max(int rt,int l,int r)
{
	if( L <= l && R >= r)return maxnum[rt];
	int mid=(l+r)>>1;
	int ans = -0x7f7f7f7f ;
	if(L <= mid )ans = std::max ( ans ,query_max(rt<<1,l,mid));
	if( R > mid ) ans = std::max ( ans ,query_max(rt<<1|1,mid+1,r));
	return ans;
}
int Query(int x,int y){
	int ans = -0x7f7f7f7f ;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])std::swap(x,y);
		L = dfn[top[x]], R = dfn[x] ;
		ans = std::max ( ans , query_max(1,1,n));
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])std::swap(x,y);
	L = dfn[son[x]] , R = dfn[y] ;
	ans = std::max ( ans ,query_max(1,1,n));
	return ans;
}
void Insert(int rt,int l,int r,int x,int w)
{
	if(l==r){maxnum[rt]=w;return;}
	int mid=(l+r)>>1;
	if(x <= mid)Insert(rt<<1,l,mid,x,w);
	else Insert(rt<<1|1,mid+1,r,x,w);
	maxnum[rt]=std::max(maxnum[rt<<1],maxnum[rt<<1|1]);
}
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",&x,&y,&z);
		Addedge(x,y,z,i);
		Addedge(y,x,z,i);
	}
	deep[1]=1;dfs1(1);dfs2(1,1);
	Build(1,1,n);
	char ch[10];
	while(1){
		scanf("%s",ch);
		if(ch[0]=='D')break;
		if(ch[0]=='C'){
			scanf("%d%d",&x,&y);
			Insert(1,1,n,dfn[pos[x]],y);
		}
		else {
			scanf("%d%d",&x,&y);
			printf("%d\n",Query(x,y));
		}
	}
}