记录编号	96165	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3237] 树的维护	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.998 s
提交时间	2014-04-11 16:04:30	内存使用	2.69 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEN=10010,INF=0x7fffffff/2;
class NODE{//线段树的节点
public:
	int left,right;
	int lc,rc;
	int mx,mn;//最大值和最小值
	bool inv;//是否应当取反
	void negate(void){
		swap(mx,mn);
		mx*=-1,mn*=-1;
		inv^=1;
	}
	void assign(int x){//整段赋x
		mx=mn=x;
		inv=false;
	}
};
int treetot;
NODE tree[SIZEN*2];
int build(int x,int y){//默认值为0
	int p=treetot++;
	NODE &now=tree[p];
	now.left=x,now.right=y;
	now.assign(0);
	if(x<y){
		int mid=(x+y)/2;
		now.lc=build(x,mid);
		now.rc=build(mid+1,y);
	}
	else now.lc=now.rc=-1;
	return p;
}
void pushdown(int root){
	if(root==-1) return;
	NODE &now=tree[root];
	if(now.lc==-1) return;
	if(now.inv){
		tree[now.lc].negate();
		tree[now.rc].negate();
		now.inv=false;
	}
}
void update(int root){
	if(root==-1) return;
	NODE &now=tree[root];
	if(now.lc==-1) return;
	NODE &lson=tree[now.lc],&rson=tree[now.rc];
	now.mx=max(lson.mx,rson.mx);
	now.mn=min(lson.mn,rson.mn);
}
void singlechange(int root,int x,int t){//改一个点的权值
	if(root==-1) return;
	pushdown(root);
	NODE &now=tree[root];
	if(now.right<x||now.left>x) return;
	if(now.lc==-1) now.assign(t);//就是这个点
	else{
		singlechange(now.lc,x,t);
		singlechange(now.rc,x,t);
		update(root);
	}
}
void segnegate(int root,int x,int y){
	if(root==-1) return;
	NODE &now=tree[root];
	pushdown(root);
	if(now.right<x||now.left>y) return;
	if(now.left>=x&&now.right<=y) now.negate();//完全取反
	else{
		segnegate(now.lc,x,y);
		segnegate(now.rc,x,y);
		update(root);
	}
}
int segmax(int root,int x,int y){
	if(root==-1) return -INF;
	NODE &now=tree[root];
	pushdown(root);
	if(now.right<x||now.left>y) return -INF;
	if(now.left>=x&&now.right<=y) return now.mx;
	else return max(segmax(now.lc,x,y),segmax(now.rc,x,y));
}
class CHAIN{//一条树链
public:
	int tpos;//对应线段树根的下标
	int top;//最上面的节点
};
CHAIN tc[SIZEN];//树链的信息
int tcnum;
int cbelong[SIZEN]={0};//属于哪一条链
int ufs[SIZEN]={0};
int grand(int x){
	return !ufs[x]?x:ufs[x]=grand(ufs[x]);
}
int segpos[SIZEN]={0};//在链中
int N;
vector<pair<int,int> > c[SIZEN];
int edgew[SIZEN]={0};//边的权重
int lv[SIZEN]={0};//边对应哪个点
int father[SIZEN]={0},depth[SIZEN]={0};
int dfslis[SIZEN*2]={0},dfslen;//dfslis的大小必须是2SIZEN,否则会跪
int dfn[SIZEN]={0};
int weight[SIZEN]={0};//点的权重
int ST[SIZEN*2][20]={0};
void ST_prepare(void){
	int m=floor(log(dfslen+0.0)/log(2.0));
	for(int i=1;i<=dfslen;i++) ST[i][0]=dfslis[i];
	for(int j=1;j<=m;j++){
		for(int i=1;i<=dfslen;i++){
			if(i+(1<<j)-1>dfslen) break;
			int x=ST[i][j-1],y=ST[i+(1<<(j-1))][j-1];
			ST[i][j]=depth[x]<depth[y]?x:y;
		}
	}
}
int STLCA(int a,int b){
	if(dfn[a]>dfn[b]) swap(a,b);
	int l=dfn[a],r=dfn[b];//[l,r]区间最浅
	int m=floor(log(r-l+1.0)/log(2.0));
	int x=ST[l][m],y=ST[r-(1<<m)+1][m];
	return depth[x]<depth[y]?x:y;
}
void grandnegate(int anc,int x){//anc~x之间的全部取反
	int k=cbelong[x],tp=tc[k].top;//tp是链的最上点
	while(depth[tp]>depth[anc]){
		segnegate(tc[k].tpos,segpos[x],segpos[tp]);
		x=father[tp];
		k=cbelong[x],tp=tc[k].top;
	}
	if(x==anc) return;
	segnegate(tc[k].tpos,segpos[x],segpos[anc]-1);
}
void pathnegate(int a,int b){
	int anc=STLCA(a,b);
	grandnegate(anc,a);
	grandnegate(anc,b);
}
int grandmax(int anc,int x){//返回anc~x之间的最大值
	int ans=-INF;
	int k=cbelong[x],tp=tc[k].top;
	while(depth[tp]>depth[anc]){
		ans=max(ans,segmax(tc[k].tpos,segpos[x],segpos[tp]));
		x=father[tp];
		k=cbelong[x],tp=tc[k].top;
	}
	if(x==anc) return ans;
	ans=max(ans,segmax(tc[k].tpos,segpos[x],segpos[anc]-1));
	return ans;
}
int getmax(int a,int b){
	int anc=STLCA(a,b);
	return max(grandmax(anc,a),grandmax(anc,b));
}
void nodechange(int x,int t){
	int k=cbelong[x];
	singlechange(tc[k].tpos,segpos[x],t);
}
int DFS(int x){//返回从x开始的链的长度
	dfslis[++dfslen]=x;dfn[x]=dfslen;
	int best=0,bestlen=0;//bestlen是最长链的长度
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i].first;
		if(u!=father[x]){
			weight[u]=edgew[c[x][i].second];
			lv[c[x][i].second]=u;
			depth[u]=depth[x]+1;
			father[u]=x;
			int now=DFS(u);
			if(now>bestlen){
				if(best){
					cbelong[best]=++tcnum;
					tc[tcnum].top=best;
					tc[tcnum].tpos=build(1,bestlen);
				}
				bestlen=now;
				best=u;
			}
			else{//u向下的链被截断
				cbelong[u]=++tcnum;
				tc[tcnum].top=u;
				tc[tcnum].tpos=build(1,now);
			}
			dfslis[++dfslen]=x;
		}
	}
	ufs[best]=x;//如果best是0不会产生影响
	segpos[x]=bestlen+1;
	return bestlen+1;
}
void globalclear(int N){//丧心病狂的单文件多数据!!!!
	treetot=0;
	tcnum=0;
	memset(cbelong,0,sizeof(cbelong));
	memset(ufs,0,sizeof(ufs));
	memset(segpos,0,sizeof(segpos));
	for(int i=1;i<=N;i++) c[i].clear();
	memset(edgew,0,sizeof(edgew));
	memset(lv,0,sizeof(lv));
	memset(father,0,sizeof(father));
	memset(depth,0,sizeof(depth));
	memset(dfslis,0,sizeof(dfslis));
	dfslen=0;
	memset(dfn,0,sizeof(dfn));
	memset(weight,0,sizeof(weight));
}
void work(void){
	char cmd[10]={0};
	int x,y,t;
	while(true){
		scanf("%s",cmd);
		if(!strcmp(cmd,"DONE")) break;
		if(!strcmp(cmd,"CHANGE")){
			scanf("%d%d",&x,&t);
			nodechange(lv[x],t);
		}
		else if(!strcmp(cmd,"NEGATE")){
			scanf("%d%d",&x,&y);
			pathnegate(x,y);
		}
		else if(!strcmp(cmd,"QUERY")){
			scanf("%d%d",&x,&y);
			printf("%d\n",getmax(x,y));
		}
	}
}
void init(void){
	int L=DFS(1);
	cbelong[1]=++tcnum;
	tc[tcnum].top=1;
	tc[tcnum].tpos=build(1,L);
	for(int i=1;i<=N;i++) cbelong[i]=cbelong[grand(i)];
	for(int i=1;i<=N;i++) nodechange(i,weight[i]);
	ST_prepare();
}
void read(void){
	scanf("%d",&N);
	globalclear(N);
	int a,b,w;
	for(int i=1;i<N;i++){
		scanf("%d%d%d",&a,&b,&w);
		edgew[i]=w;
		c[a].push_back(make_pair(b,i));
		c[b].push_back(make_pair(a,i));
	}
}
int main(){
	freopen("maintaintree.in","r",stdin);
	freopen("maintaintree.out","w",stdout);
	read();
	init();
	work();
	/*int T;
	scanf("%d",&T);
	while(T--){
		read();
		init();
		work();
	}*/
	return 0;
}