记录编号	153653	评测结果	AAAAAAAAAA
题目名称	[SPOJ 375] 难存的情缘	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.179 s
提交时间	2015-03-18 17:24:09	内存使用	1.50 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int INF=1e9;
int i,n,p,zj1,zj2,zj3,ans;
int ROOT[10000]={0};
struct LINK{int fa,son,s,dep,w,z,ret,Root;}A[10010];
struct tree{int fa,ri,le,Max,L,R;}B[20010];
int C[10010]={0},Num,sj=1;
char str[10];

int to[20000]={0},ne[20000]={0},w[20000]={0},head[10000]={0},cor[20000]={0};
inline void addedge(int u,int v,int c)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=c;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj,w[sj]=c;
}

inline void make_tree(int x,int l,int r)
{
	B[x].L=l,B[x].R=r;
	if(l==r){A[C[l]].ret=x,A[C[l]].z=l,B[x].Max=A[C[l]].w;return;}
	
	B[x].le=++Num,B[Num].fa=x;make_tree(Num,l,(l+r)>>1);
	B[x].ri=++Num,B[Num].fa=x;make_tree(Num,((l+r)>>1)+1,r);
	
	B[x].Max=max(B[B[x].le].Max,B[B[x].ri].Max);
}

inline void dfs_1(int x,int y)
{
	A[x].fa=y,A[x].s=1,A[x].dep=A[y].dep+1;
	for(int h=head[x];h;h=ne[h])if(to[h]!=y)
	{
		A[to[h]].w=w[h],cor[h>>1]=to[h];
		dfs_1(to[h],x);A[x].s+=A[to[h]].s;
		if(!A[x].son||(A[A[x].son].s<A[to[h]].s))A[x].son=to[h];
	}
}
inline void dfs_2(int x,int y)
{
	C[++C[0]]=x;A[x].Root=A[y].Root;
	if(x!=A[y].son)A[x].Root=x;
	if(A[x].son)dfs_2(A[x].son,x);else
	ROOT[A[x].Root]=++Num,make_tree(Num,1,C[0]),C[0]=0;
	for(int h=head[x];h;h=ne[h])
	if(to[h]!=y&&to[h]!=A[x].son)dfs_2(to[h],x);
}
void init()
{
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&zj1,&zj2,&zj3);
		addedge(zj1,zj2,zj3);
	}
	dfs_1(1,1);dfs_2(1,1);
}

inline void Change(int x,int y)
{
	A[x].w=y;x=A[x].ret;B[x].Max=y;x=B[x].fa;
	while(x)
	B[x].Max=max(B[B[x].le].Max,B[B[x].ri].Max),x=B[x].fa;
}

inline void Findmax(int x,int ll,int rr)
{
	if(ll<=B[x].L&&rr>=B[x].R)
	{if(ans<B[x].Max)ans=B[x].Max;return;}
	
	int mid=(B[x].L+B[x].R)>>1;if(mid>=ll&&mid<rr)
	{Findmax(B[x].le,ll,mid);Findmax(B[x].ri,mid+1,rr);}
	else if(mid<ll)Findmax(B[x].ri,ll,rr);
	else Findmax(B[x].le,ll,rr);
}
 
inline void Query(int u,int v)
{
	ans=-INF;
	while(A[u].Root!=A[v].Root)
	{
		if(A[A[u].Root].dep<A[A[v].Root].dep)
		zj3=u,u=v,v=zj3;
		Findmax(ROOT[A[u].Root],1,A[u].z);
		u=A[u].Root,u=A[u].fa;
	}
	if(u!=v)
	{
		if(A[u].dep>A[v].dep)zj3=u,u=v,v=zj3;
		Findmax(ROOT[A[u].Root],A[A[u].son].z,A[v].z);
	}
	printf("%d\n",ans);
}

void work()
{
	while(1)
	{
		scanf("%s",str);
		if(str[0]=='C')
		{
			scanf("%d%d",&zj1,&zj2);
			Change(cor[zj1],zj2);
		}
		else if(str[0]=='Q')
		{
			scanf("%d%d",&zj1,&zj2);
			Query(zj1,zj2);
		}
		else break;
	}
}
int main()
{
	freopen("qtree.in","r",stdin);
	freopen("qtree.out","w",stdout);
	init();
	work();
	return 0;
}