记录编号	458842	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.362 s
提交时间	2017-10-11 21:09:57	内存使用	1.49 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
vector<int>p[maxn];
int n,tot;
int w[maxn],fa[maxn],dep[maxn],idx[maxn],son[maxn],top[maxn],siz[maxn],rank[maxn];
struct tree{
	int l,r,neg,maxx,minn;
}tr[maxn*4];
void dfs1(int x){
	siz[x]=1;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i];
		if(u==fa[x])continue;
		fa[u]=x,dep[u]=dep[x]+1;
		dfs1(u);
		siz[x]+=siz[u];
		if(!son[x]||siz[u]>siz[son[x]])son[x]=u;
	}
}
void dfs2(int x,int y){
	top[x]=y,idx[x]=++tot,rank[idx[x]]=x;
	if(!son[x])return;
	dfs2(son[x],y);
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i];
		if(u!=son[x]&&u!=fa[x])dfs2(u,u);
	}
}
void updata(int x){
	tr[x].maxx=max(tr[x<<1].maxx,tr[x<<1^1].maxx);
	tr[x].minn=min(tr[x<<1].minn,tr[x<<1^1].minn);
}
void downdata(int x){
	if(tr[x].neg){
		if(tr[x].l!=tr[x].r){
			tr[x<<1].neg^=1,tr[x<<1^1].neg^=1;
			swap(tr[x<<1].maxx,tr[x<<1].minn);
			swap(tr[x<<1^1].maxx,tr[x<<1^1].minn);
			tr[x<<1].minn*=-1,tr[x<<1].maxx*=-1;
			tr[x<<1^1].minn*=-1,tr[x<<1^1].maxx*=-1;
		}
		tr[x].neg=0;
	}
}
void buildtree(int x,int l,int r){
	tr[x].l=l,tr[x].r=r,tr[x].neg=0;
	if(l==r)tr[x].maxx=tr[x].minn=w[rank[l]];
	else{
		int mid=(l+r)>>1;
		buildtree(x<<1,l,mid);
		buildtree(x<<1^1,mid+1,r);
		updata(x);
	}
}
void change(int x,int d,int c){
	if(tr[x].l==tr[x].r)tr[x].maxx=tr[x].minn=c;
	else{
		downdata(x);
		if(d<=tr[x<<1].r)change(x<<1,d,c);
		else change(x<<1^1,d,c);
		updata(x);
	}
}
int maxx(int x,int l,int r){
	if(l<=tr[x].l&&tr[x].r<=r)return tr[x].maxx;
	else{
		downdata(x);
		int ans=-(int)1e9;
		if(l<=tr[x<<1].r)ans=maxx(x<<1,l,r);
		if(tr[x<<1^1].l<=r)ans=max(ans,maxx(x<<1^1,l,r));
		updata(x);
		return ans;
	}
}
void negate(int x,int l,int r){
	if(l<=tr[x].l&&tr[x].r<=r){
		tr[x].neg^=1;
		swap(tr[x].maxx,tr[x].minn);
		tr[x].maxx*=-1,tr[x].minn*=-1;
	}
	else{
		downdata(x);
		if(l<=tr[x<<1].r)negate(x<<1,l,r);
		if(tr[x<<1^1].l<=r)negate(x<<1^1,l,r);
		updata(x);
	}
	
}
int findmax(int x,int y){
	int f1=top[x],f2=top[y],ans=-(int)1e9;
	while(f1!=f2){
		if(dep[f1]<dep[f2])swap(f1,f2),swap(x,y);
		ans=max(ans,maxx(1,idx[f1],idx[x]));
		x=fa[f1],f1=top[x];
	}
	ans=max(ans,(dep[x]>dep[y])?maxx(1,idx[y]+1,idx[x]):maxx(1,idx[x]+1,idx[y]));
	return ans;
}
void reverse(int x,int y){
	int f1=top[x],f2=top[y];
	while(f1!=f2){
		if(dep[f1]<dep[f2])swap(f1,f2),swap(x,y);
		negate(1,idx[f1],idx[x]);
		x=fa[f1],f1=top[x];
	}
	if(x==y)return;
	if(dep[x]>dep[y])swap(x,y);
	negate(1,idx[x]+1,idx[y]);//因把边权变为点权，而一条链是连续的，所以+1
}
int main(){
	freopen("maintaintree.in","r",stdin);
	freopen("maintaintree.out","w",stdout);
	scanf("%d",&n);
	int u,v,x,t[maxn];
	char q[10];
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&u,&v,&x);
		if(u>v)swap(u,v);
		w[v]=x,t[i]=v,p[u].push_back(v),p[v].push_back(u);
	}
	dfs1(1),dfs2(1,1);
	buildtree(1,1,n);
	scanf("%s",&q);
	while(q[0]!='D'){
		scanf("%d%d",&u,&v);
		if(q[0]=='C')change(1,idx[t[u]],v);
		else if(q[0]=='N')reverse(u,v);
		else printf("%d\n",findmax(u,v));
		scanf("%s",&q);
	}
	return 0;
}