记录编号	296262	评测结果	AAAAAAAAAA
题目名称	[SPOJ 375] 难存的情缘	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.568 s
提交时间	2016-08-15 07:03:05	内存使用	0.98 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lch l,mid,rt<<1
#define rch mid+1,r,rt<<1|1
using namespace std;
const int maxn=10010;
struct edge{
	int to,data,pos,prev;
}e[maxn<<1];
void insert(int,int,int);
void dfs1(int);
void dfs2(int,int);
void build(int,int,int);
int query(int,int);
int query(int,int,int,int,int);
void change(int,int,int,int,int);
int n,a[maxn<<2],x,y,z,len=0,tim=0;
int first[maxn],depth[maxn],prt[maxn],son[maxn],top[maxn],size[maxn],sone[maxn];
int last[maxn],data[maxn];
char c[15];
int main(){
#define MINE
#ifdef MINE
	freopen("qtree.in","r",stdin);
	freopen("qtree.out","w",stdout);
#endif
	memset(last,-1,sizeof(last));
	depth[1]=1;
	son[0]=top[0]=size[0]=0;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		insert(x,y,z);
		insert(y,x,z);
	}
	dfs1(1);
	//printf("dfn: ");
	dfs2(1,1);
	//printf("\ntop: ");
	//for(int i=1;i<=n;i++)printf(" %d",top[i]);
	//printf("\ndata: ");
	//for(int i=1;i<=n;i++)printf(" %d",data[i]);
	//printf("\n");
	build(1,n,1);
	while(scanf("%s%d%d",c,&x,&y)==3){
		if(!strcmp(c,"DONE"))break;
		else if(!strcmp(c,"CHANGE")){
			x=(x-1)<<1;
			e[x].data=e[x^1].data=y;
			change(e[x].pos,y,1,n,1);
		}
		else if(!strcmp(c,"QUERY")){
			printf("%d\n",query(x,y));
		}
	}
	return 0;
}
void insert(int x,int y,int z){
	e[len].to=y;
	e[len].data=z;
	e[len].prev=last[x];
	last[x]=len++;
}
void dfs1(int x){
	int y;
	size[x]=1;
	for(int i=last[x];i!=-1;i=e[i].prev){
		y=e[i].to;
		if(y==prt[x])continue;
		prt[y]=x;
		depth[y]=depth[x]+1;
		dfs1(y);
		size[x]+=size[y];
		if(size[y]>size[son[x]]){
			son[x]=y;
			sone[x]=i;
		}
	}
}
void dfs2(int x,int tp){
	int y;
	first[x]=++tim;
	//printf(" %d",x);
	top[x]=tp;
	if(son[x]){
		dfs2(son[x],tp);
		data[first[son[x]]]=e[sone[x]].data;
		e[sone[x]].pos=e[sone[x]^1].pos=first[son[x]];
	}
	for(int i=last[x];i!=-1;i=e[i].prev){
		y=e[i].to;
		if(y==prt[x]||y==son[x])continue;
		dfs2(y,y);
		data[first[y]]=e[i].data;
		e[i].pos=e[i^1].pos=first[y];
	}
}
void build(int l,int r,int rt){
	if(l==r){
		a[rt]=data[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lch);
	build(rch);
	a[rt]=max(a[rt<<1],a[rt<<1|1]);
}
int query(int x,int y){
	int ans=0,fx=top[x],fy=top[y];
	while(fx!=fy){
		if(depth[fx]<depth[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		ans=max(ans,query(first[fx],first[x],1,n,1));
		//printf("%d %d\n",first[fx],first[x]);
		x=prt[fx];
		fx=top[x];
	}
	if(depth[x]>depth[y])swap(x,y);
	if(x!=y)ans=max(ans,query(first[x]+1,first[y],1,n,1));
	//printf("%d %d\n",first[x],first[y]);
	return ans;
}
int query(int s,int t,int l,int r,int rt){
	if(s<=l&&t>=r)return a[rt];
	int mid=(l+r)>>1;
	if(t<=mid)return query(s,t,lch);
	if(s>mid)return query(s,t,rch);
	return max(query(s,t,lch),query(s,t,rch));
}
void change(int p,int x,int l,int r,int rt){
	if(l==r){
		a[rt]=x;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid)change(p,x,lch);
	else change(p,x,rch);
	a[rt]=max(a[rt<<1],a[rt<<1|1]);
}
/*
6
1 2 1
1 3 2
3 4 3
4 6 2
3 5 4
QUERY 2 6
QUERY 5 6
QUERY 1 4
*/