实在是看不出来有什么问题了......

记录

#include<iostream>
#include<memory.h>
#include<cmath>
#include<stdlib.h>

#define maxn 200005
#define int long long

using namespace std; 

struct edge{
	int to;
	int next;
	int val;
}e[2*maxn];

int cnt=1;
int head[maxn];

void add(int u,int v,int w){
	e[cnt].val=w;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt++;
}

int n;
int arr[maxn];
//用每一条边的下面的节点来存储边 

int dfs_cnt=1;
int sz[maxn],depth[maxn],fa[maxn],son[maxn];
int root[maxn];
int mapping[maxn],q_map[maxn];

int seg_cnt=1;
int l[4*maxn],r[4*maxn],lc[4*maxn],rc[4*maxn];
int f[4*maxn],sum[4*maxn],ma[4*maxn],mi[4*maxn];

void dfs1(int x,int father){
	
	fa[x]=father;
	depth[x]=depth[father]+1;
	sz[x]=1;
	
	mapping[dfs_cnt]=x;
	q_map[x]=dfs_cnt++;
	
	for(int i=head[x];i;i=e[i].next){
		if(e[i].to==fa[x]){
			continue;
		}
		arr[e[i].to]=e[i].val;
		dfs1(e[i].to,x);
		sz[x]+=sz[e[i].to];
		if(sz[son[x]]<sz[e[i].to]){
			son[x]=e[i].to;
		}
	}
	
}

void dfs2(int x,int rt){
	
//	cout<<"x="<<x<<" father="<<fa[x]<<endl;
	
	root[x]=rt;
	
	if(son[x]){
		dfs2(son[x],rt);
	}
	
	for(int i=head[x];i;i=e[i].next){
		if(e[i].to==fa[x]||e[i].to==son[x]){
			continue;
		}
		dfs2(e[i].to,e[i].to);
	}
	
}

void push_up(int x){
	sum[x]=sum[lc[x]]*f[lc[x]]+sum[rc[x]]*f[rc[x]];
	ma[x]=max(max(ma[lc[x]]*f[lc[x]],mi[lc[x]]*f[lc[x]]),\
	max(ma[rc[x]]*f[rc[x]],mi[rc[x]]*f[rc[x]]));
	mi[x]=min(min(ma[lc[x]]*f[lc[x]],mi[lc[x]]*f[lc[x]]),\
	min(ma[rc[x]]*f[rc[x]],mi[rc[x]]*f[rc[x]]));
}

void push_down(int x){
	f[lc[x]]*=f[x];
	f[rc[x]]*=f[x];
	f[x]=1;
	push_up(x);
}

void build(int x,int left,int right){
	
//	cout<<"x="<<x<<endl;
	
	l[x]=left;
	r[x]=right;
	f[x]=1;
	
	if(left==right){
		sum[x]=mi[x]=ma[x]=arr[mapping[left]];
		return;
	}
	
	int mid=left+right>>1;
	lc[x]=seg_cnt++;
	build(lc[x],left,mid);
	rc[x]=seg_cnt++;
	build(rc[x],mid+1,right);
	
	push_up(x);
	
}

void change_on_tree(int x,int goal,int val){
	if(l[x]==r[x]){
		sum[x]=mi[x]=ma[x]=abs(val);
		f[x]=val/abs(val);
		return;
	}
	
	push_down(x);
	
	int mid=l[x]+r[x]>>1;
	if(goal<=mid){
		change_on_tree(lc[x],goal,val);
	}else{
		change_on_tree(rc[x],goal,val);
	}
	
	push_up(x);
}

void change_on_tree_2(int x,int left,int right){
	
	if(left<=l[x]&&r[x]<=right){
		f[x]*=-1;
		return;
	}
	
	push_down(x);
	
	int mid=l[x]+r[x]>>1;
	if(left<=mid){
		change_on_tree_2(lc[x],left,right);
	}
	if(right>mid){
		change_on_tree_2(rc[x],left,right);
	}
	
	push_up(x);
}

void change(int u,int v){
	
	while(root[u]!=root[v]){
		if(depth[root[u]]<depth[root[v]]){
			int ch=u;
			u=v;
			v=ch;
		}
		
		change_on_tree_2(0,q_map[root[u]],q_map[u]);
		u=fa[root[u]];
		
	}
	
	if(depth[u]>depth[v]){
		int ch=v;
		v=u;
		u=ch;
	}
	if(u!=v){
		change_on_tree_2(0,q_map[u]+1,q_map[v]);
	}
	
	
}

int query_sum_on_tree(int x,int left,int right){
	if(left<=l[x]&&r[x]<=right){
		return sum[x]*f[x];
	}
	
	int lre=0,mid=l[x]+r[x]>>1;
	
	push_down(x);
	
	if(left<=mid){
		lre+=query_sum_on_tree(lc[x],left,right);
	}
	if(right>mid){
		lre+=query_sum_on_tree(rc[x],left,right);
	}
	
	push_up(x);
	return lre;
}

int query_sum(int u,int v){
//	cout<<u<<" "<<v<<endl;
	int lre=0;
//	cout<<"root:"<<root[u]<<","<<root[v]<<endl;
	while(root[u]!=root[v]){
		if(depth[root[u]]<depth[root[v]]){
			int ch=u;
			u=v;
			v=ch;
		}
		
	//	cout<<root[u]<<" "<<u<<" "<<query_on_tree(0,q_map[root[u]],q_map[u])<<endl;
		
		lre+=query_sum_on_tree(0,q_map[root[u]],q_map[u]);
		u=fa[root[u]];
	}
	if(depth[u]>depth[v]){
		int ch=u;
		u=v;
		v=ch;
	}
	if(u!=v){
	//	cout<<u<<" "<<v<<endl;
	//	cout<<u<<" "<<v<<" "<<query_sum_on_tree(0,q_map[u]+1,q_map[v])<<endl;
		lre+=query_sum_on_tree(0,q_map[u]+1,q_map[v]);
	}
	return lre;
}

int query_max_on_tree(int x,int left,int right){
	
	if(left<=l[x]&&r[x]<=right){
		return max(f[x]*ma[x],f[x]*mi[x]);
	}
	
	push_down(x);
	
	int mid=l[x]+r[x]>>1,lre=-1005;
	if(left<=mid){
		lre=max(lre,query_max_on_tree(lc[x],left,right));
	}
	if(mid<right){
		lre=max(lre,query_max_on_tree(rc[x],left,right));
	}
	
	push_up(x);
	
	return lre;
}

int query_max(int u,int v){
	int lre=-1005;
	while(root[u]!=root[v]){
		if(depth[root[u]]<depth[root[v]]){
			int ch=v;
			v=u;
			u=ch;
		}
		
		lre=max(lre,query_max_on_tree(0,q_map[root[u]],q_map[u]));
		u=fa[root[u]];
		
	}
	
	if(depth[u]>depth[v]){
		int ch=v;
		v=u;
		u=ch;
	}
	if(u!=v){
		lre=max(lre,query_max_on_tree(0,q_map[u]+1,q_map[v]));
	}
	
	return lre;
}

int query_min_on_tree(int x,int left,int right){
	
	if(left<=l[x]&&r[x]<=right){
		return min(f[x]*ma[x],f[x]*mi[x]);
	}
	
	push_down(x);
	
	int mid=l[x]+r[x]>>1,lre=1005;
	if(left<=mid){
		lre=min(lre,query_min_on_tree(lc[x],left,right));
	}
	if(mid<right){
		lre=min(lre,query_min_on_tree(rc[x],left,right));
	}
	
	push_up(x);
	
	return lre;
}

int query_min(int u,int v){
	int lre=1005;
	while(root[u]!=root[v]){
		if(depth[root[u]]<depth[root[v]]){
			int ch=v;
			v=u;
			u=ch;
		}
		
		lre=min(lre,query_min_on_tree(0,q_map[root[u]],q_map[u]));
		u=fa[root[u]];
		
	}
	
	if(depth[u]>depth[v]){
		int ch=v;
		v=u;
		u=ch;
	}
	if(u!=v){
		lre=min(lre,query_min_on_tree(0,q_map[u]+1,q_map[v]));
	}
	
	return lre;
}

void show_data(){
	for(int i=1;i<=n;i++){
		cout<<"i="<<i<<" "<<root[i]<<" "<<fa[i]<<" "<<depth[i]<<endl;
	}
}

void show_tree(){
	for(int i=0;i<cnt;i++){
		cout<<"i="<<i<<" "<<l[i]<<" "<<r[i]<<" "<<sum[i]<<" "<<f[i]<<endl; 
	}
}

signed main(){
	
	freopen("P1505_1.in","r",stdin);
	
	memset(head,0,sizeof(head));
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		u++;
		v++;
		add(u,v,w);
		add(v,u,w);
	}
	
	dfs1(1,0);
//	cout<<"%"<<endl;
	dfs2(1,1);
//	cout<<"%"<<endl;
	build(0,1,n);
	
//	show_data();
	
	int m,u,v;
	string opt;
	
	cin>>m;
	while(m--){
		cin>>opt>>u>>v;
		if(opt[0]=='C'){
			u++;
			change_on_tree(0,q_map[u],v);
		}else if(opt[0]=='N'){
			u++;
			v++;
			change(u,v);
		}else if(opt[0]=='S'){
			u++;
			v++;
		//	cout<<u<<" "<<v<<endl;
		//	show_tree();
			cout<<query_sum(u,v)<<endl;
		}else if(opt[1]=='A'){
			u++;
			v++;
			cout<<query_max(u,v)<<endl;
		}else{
			u++;
			v++;
			cout<<query_min(u,v)<<endl;
		}
	}
	
	return 0;
}
/*

*/