记录编号	271986	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	1.143 s
提交时间	2016-06-16 14:49:34	内存使用	44.17 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=500100;
const int Info=-0x3fffffff;
struct Node
{
	int to,next,dis,num;
}edge[maxn];
int head[maxn]={0},tot=0;
void Addedge(int x,int y,int w,int z)
{
	edge[++tot].to=y;
	edge[tot].num=z;
	edge[tot].next=head[x];
	edge[tot].dis=w;
	head[x]=tot;
}
int size[maxn]={0},fa[maxn]={0},top[maxn]={0},son[maxn]={0},deep[maxn]={0},cnt=0,B[maxn]={0};
int f[maxn]={0},dis[maxn]={0};
int maxnum[maxn<<2]={0},minnum[maxn<<2]={0},lazy[maxn]={0},Qx=0,Qy=0,n=0,ans=0;
int dfn_pos[maxn]={0};
void Swap(int &a,int &b)
{
	int tmp=a;
	a=-b;
	b=-tmp;
}
void Update(int rt)
{
	if(lazy[rt])
	{
		Swap(maxnum[rt<<1],minnum[rt<<1]);
		Swap(maxnum[rt<<1|1],minnum[rt<<1|1]);
		lazy[rt<<1]=!lazy[rt<<1];
		lazy[rt<<1|1]=!lazy[rt<<1|1];
		lazy[rt]=0;
	}
} 
void Build(int rt,int l,int r)
{
	if(l==r)
	{
		maxnum[rt]=minnum[rt]=dis[ dfn_pos[l] ];
		return;
	}
	int mid=(l+r)>>1;
	Build(rt<<1,l,mid);
	Build(rt<<1|1,mid+1,r);
	maxnum[rt]=max(maxnum[rt<<1],maxnum[rt<<1|1]);
	minnum[rt]=min(minnum[rt<<1],minnum[rt<<1|1]);
}
int Query(int rt,int l,int r)
{
	if( Qx<=l && Qy>=r )
	{
		return maxnum[rt];
	}
	Update(rt);
	int mid=(l+r)>>1;
	int ret=Info;//更新ans ！！
	if(Qx<=mid)ret=max(ret,Query(rt<<1,l,mid));
	if(Qy>mid)ret=max(ret,Query(rt<<1|1,mid+1,r));
	return ret;
}///////////////
int query(int l,int r)
{
	Qx=l;
	Qy=r;
	return Query(1,1,n);
}
void Insert(int rt,int l,int r,int k,int w)
{
	if(l==r)
	{
		minnum[rt]=maxnum[rt]=w;
		return;
	}
	Update(rt);
	int mid=(l+r)>>1;
	if(k<=mid)Insert(rt<<1,l,mid,k,w);
	else Insert(rt<<1|1,mid+1,r,k,w);
	maxnum[rt]=max(maxnum[rt<<1],maxnum[rt<<1|1]);
	minnum[rt]=min(minnum[rt<<1],minnum[rt<<1|1]);
}
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])
		{
			fa[p]=x;
			deep[p]=deep[x]+1;
			B[ edge[i].num ]=p;
			dis[p]=edge[i].dis;
			dfs1(p);
			size[x]+=size[p];
			if(size[p] > size[ son[x] ])
			{
				son[x]=p;
			}
		}
	}
}
void dfs2(int x,int tp)
{
	top[x]=tp;
	f[x]=++cnt;
	dfn_pos[cnt]=x;
	if(son[x])
	{
		dfs2(son[x],tp);
	}
	for(int i=head[x];i;i=edge[i].next)
	{
		int p=edge[i].to;
		if(!f[p])
		{
			dfs2(p,p);
		}
	}
}
int Q_ask(int x,int y)
{
	int ans=Info;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]])
		{
			swap(x,y);
		//	swap(fx,fy);
		}
		ans=max( ans,query( f[top[x]],f[x] ));
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])
	{
		swap(x,y);
	}
	ans=max( ans, query( f[ son[x] ],f[y] ));
	return ans;
}
void _negate(int rt,int l,int r,int a,int b)
{
	if(a<=l&&b>=r)
	{
		lazy[rt]=!lazy[rt];
		Swap(minnum[rt],maxnum[rt]);
		return;
	}
	Update(rt);
	int mid=(l+r)>>1;
	if(a<=mid)_negate(rt<<1,l,mid,a,b);
	if(b>mid)_negate(rt<<1|1,mid+1,r,a,b);
	maxnum[rt]=max(maxnum[rt<<1],maxnum[rt<<1|1]);
	minnum[rt]=min(minnum[rt<<1],minnum[rt<<1|1]);
}	
void Negate(int x,int y)
{
//	int fx=top[x],fy=top[y];
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]])
		{
			swap(x,y);
		}
		_negate(1,1,n,f[top[x]],f[x]);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])
	{
		swap(x,y);
	}
	_negate(1,1,n,f[ son[x] ],f[y]);
}
int main()
{
	freopen("maintaintree.in","r",stdin);freopen("maintaintree.out","w",stdout);
	deep[1]=1;
	scanf("%d",&n);
	int a,b,w;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&a,&b,&w);
		Addedge(a,b,w,i);
		Addedge(b,a,w,i);
	}
	dfs1(1);
	dfs2(1,1);
	Build(1,1,n);
	char s[10];
	while(1)
	{
		scanf("%s",s);
		if(s[0]=='D')break;
		scanf("%d%d",&a,&b);
		if(s[0]=='Q')
		{
			printf("%d\n",Q_ask(a,b));
		}
		else if(s[0]=='C')
		{
			Insert(1,1,n,f[ B[a] ],b);
		}
		else
		{
			Negate(a,b);
		}
	}
	return 0;
}