记录编号	142841	评测结果	AAAAAAAAAA
题目名称	[国家集训队2011]旅游	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.257 s
提交时间	2014-12-11 09:11:41	内存使用	25.88 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=100010,INF=0x7fffffff/2;
class Data{
public:
	int mn,mx,sum;
	void operator = (int x){mn=mx=sum=x;}
};
Data operator + (Data a,Data b){
	a.mn=min(a.mn,b.mn);
	a.mx=max(a.mx,b.mx);
	a.sum+=b.sum;
	return a;
}
const Data Zero_Data=(Data){INF,-INF,0};//一个"无影响"的Data值
class Node{//线段树的节点
public:
	int a,b;
	int lc,rc;
	bool inv;
	Data key;
	void Inverse(void){//取反
		inv^=1;
		key.sum*=-1;key.mn*=-1;key.mx*=-1;
		swap(key.mn,key.mx);
	}
};
class Segment_Tree{
public:
	Node Tree[SIZEN*2];
	int tot;
	void Clear(void){tot=0;}
	Segment_Tree(void){Clear();}
	void Update(int p){
		if(!p) return;
		Node &now=Tree[p];
		if(!now.lc) return;
		now.key=Tree[now.lc].key+Tree[now.rc].key;
	}
	void Push_Down(int p){
		if(!p) return;
		Node &now=Tree[p];
		if(!now.lc) return;
		if(now.inv){
			Tree[now.lc].Inverse();
			Tree[now.rc].Inverse();
			now.inv=0;
		}
	}
	int Build(int a[],int l,int r){//把序列a建树
		int p=++tot;
		Node &now=Tree[p];
		now.a=l,now.b=r,now.inv=0;
		if(l==r){
			now.lc=now.rc=0;
			now.key=a[l];
		}
		else{
			int mid=(l+r)/2;
			now.lc=Build(a,l,mid);
			now.rc=Build(a,mid+1,r);
			Update(p);
		}
		return p;
	}
	void Modify_Single(int p,int x,int t){//在p中把x改成t
		if(!p) return;
		Push_Down(p);
		Node &now=Tree[p];
		if(now.a>x||now.b<x) return;
		if(now.a==x&&now.b==x) now.key=t;
		else{
			Modify_Single(now.lc,x,t);
			Modify_Single(now.rc,x,t);
			Update(p);
		}
	}
	void Modify_Inverse(int p,int x,int y){//在p中把[x,y]取反
		if(!p) return;
		Push_Down(p);
		Node &now=Tree[p];
		if(now.a>y||now.b<x) return;
		if(now.a>=x&&now.b<=y) now.Inverse();
		else{
			Modify_Inverse(now.lc,x,y);
			Modify_Inverse(now.rc,x,y);
			Update(p);
		}
	}
	Data Query(int p,int l,int r){
		if(!p) return Zero_Data;
		Push_Down(p);
		Node &now=Tree[p];
		if(now.a>r||now.b<l) return Zero_Data;
		if(now.a>=l&&now.b<=r) return now.key;
		return Query(now.lc,l,r)+Query(now.rc,l,r);
	}
};
class Edge{
public:
	int to,id,w;
};
vector<Edge> G[SIZEN];
void Add_Edge(int a,int b,int id,int w){
	G[a].push_back((Edge){b,id,w});
}
int N;
Segment_Tree SGT;
int root[SIZEN]={0},top[SIZEN]={0};
int depth[SIZEN]={0},height[SIZEN]={0};
int fa[SIZEN]={0},falen[SIZEN]={0};
int belong[SIZEN]={0};
int Vid[SIZEN]={0};//对应的点(父子边对应其儿子)
int DFS_lis[SIZEN*2],DFS_len=0;
int vistim[SIZEN];
int ST[SIZEN*2][18];
int log_2(int x){
	int ans=-1;
	while(x) x>>=1,ans++;
	return ans;
}
int ST_LCA(int a,int b){
	int l=vistim[a],r=vistim[b];
	if(l>r) swap(l,r);
	int m=log_2(r-l+1);
	int x=ST[l][m],y=ST[r-(1<<m)+1][m];
	return depth[x]<depth[y]?x:y;
}
void ANC_Path_Inverse(int a,int b){//a是b的祖先
	if(depth[a]>=depth[b]) return;
	while(b){
		int k=belong[b];
		int l=max(depth[a]+1,depth[top[k]]);
		SGT.Modify_Inverse(root[k],l,depth[b]);
		if(depth[fa[top[k]]]>depth[a]) b=fa[top[k]];
		else break;
	}
}
void Path_Inverse(int a,int b){//路径翻转
	int g=ST_LCA(a,b);
	ANC_Path_Inverse(g,a);
	ANC_Path_Inverse(g,b);
}
void Edge_Modify(int x,int t){//x号路径改为t
	int u=Vid[x];
	SGT.Modify_Single(root[belong[u]],depth[u],t);
}
Data ANC_Path_Query(int a,int b){//a是b的祖先
	if(depth[a]>=depth[b]) return Zero_Data;
	Data ans=Zero_Data;
	while(b){
		int k=belong[b];
		int l=max(depth[a]+1,depth[top[k]]);
		ans=ans+SGT.Query(root[k],l,depth[b]);
		if(depth[fa[top[k]]]>depth[a]) b=fa[top[k]];
		else break;
	}
	return ans;
}
Data Path_Query(int a,int b){//路径查询
	int g=ST_LCA(a,b);
	return ANC_Path_Query(g,a)+ANC_Path_Query(g,b);
}
void Process(void){
	int Q;
	scanf("%d",&Q);
	char cmd[10]={0};
	int x,y;
	for(int i=1;i<=Q;i++){
		scanf("%s",cmd);
		scanf("%d%d",&x,&y);
		if(cmd[0]=='C') Edge_Modify(x,y);
		else if(cmd[0]=='N') Path_Inverse(x+1,y+1);
		else{
			Data D=Path_Query(x+1,y+1);
			if(cmd[0]=='S') printf("%d\n",D.sum);
			else if(cmd[1]=='A') printf("%d\n",D.mx);
			else if(cmd[1]=='I') printf("%d\n",D.mn);
		}
	}
}
void ST_LCA_Prepare(void){
	int m=log_2(DFS_len);
	for(int i=1;i<=DFS_len;i++) ST[i][0]=DFS_lis[i];
	for(int j=1;j<=m;j++){
		for(int i=1;i<=DFS_len;i++){
			if(i+(1<<j)-1>DFS_len) continue;
			int x=ST[i][j-1],y=ST[i+(1<<(j-1))][j-1];
			ST[i][j]=depth[x]<depth[y]?x:y;
		}
	}
}
void DFS(int x){
	height[x]=0;
	belong[x]=x;
	DFS_lis[++DFS_len]=x;
	vistim[x]=DFS_len;
	for(int i=0;i<G[x].size();i++){
		Edge &e=G[x][i];
		if(e.to!=fa[x]){
			fa[e.to]=x;falen[e.to]=e.w;
			depth[e.to]=depth[x]+1;
			Vid[e.id]=e.to;
			DFS(e.to);
			if(height[e.to]+1>height[x]){
				height[x]=height[e.to]+1;
				belong[x]=belong[e.to];
			}
			DFS_lis[++DFS_len]=x;
		}
	}
}
void Init_Chain(int x){//从x向上
	static int W[SIZEN];
	int y=x;
	W[depth[x]]=falen[x];
	while(fa[y]&&belong[fa[y]]==x){
		y=fa[y];
		W[depth[y]]=falen[y];
	}
	root[x]=SGT.Build(W,depth[y],depth[x]);
	top[x]=y;
}
void Prepare(void){
	depth[1]=fa[1]=DFS_len=0;
	DFS(1);
	ST_LCA_Prepare();
	for(int i=1;i<=N;i++)
		if(belong[i]==i) Init_Chain(i);
}
void Read(void){
	scanf("%d",&N);
	int u,v,w;
	for(int i=1;i<N;i++){
		scanf("%d%d%d",&u,&v,&w);
		u++,v++;
		Add_Edge(u,v,i,w);
		Add_Edge(v,u,i,w);
	}
}
int main(){
	freopen("nt2011_travel.in","r",stdin);
	freopen("nt2011_travel.out","w",stdout);
	Read();
	Prepare();
	Process();
	return 0;
}