这是一道树剖板题，只 AC 了 #1 和 #2 以及 Hack 数据，其他都 TLE 掉了。下载了 #3 数据，发现 $n=m=6000$，本机却跑了 4s，答案正确，看来是时间复杂度写假了，却不知道是哪里的问题，请 dalao 帮忙看看代码，谢谢！

#include<bits/stdc++.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)<(b)?(b):(a))
using namespace std;
const int buffer_size=1e5+5;
char buf[buffer_size],*S,*T;
inline char read_char()
{
    if(S==T) T=(S=buf)+fread(buf,1,buffer_size,stdin);
    return S!=T?*(S++):EOF;
}
inline int read_int()
{
    bool flag=false;
    char c=read_char();
    while(c<'0'||c>'9')
    {
        flag=(c=='-'?true:flag);
        c=read_char();
    }
    int x=0;
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c-'0');
        c=read_char();
    }
    return flag?-x:x;
}
inline void read_string(char *s)
{
	char c=read_char();
	while(c<'A'||c>'Z') c=read_char();
	while(c>='A'&&c<='Z')
	{
		*(s++)=c;
		c=read_char(); 
	}
}
int n,m;
const int V=2e5+5;
const int E=4e5+5;
int End[E],Last[V],Next[E],Len[E],e=1;
inline void add_edge(int x,int y,int z)
{
	End[++e]=y;
	Next[e]=Last[x];
	Last[x]=e;
	Len[e]=z;
	End[++e]=x;
	Next[e]=Last[y];
	Last[y]=e;
	Len[e]=z;
}
int dep[V],size[V],fath[V],son[V];
void dfs1(int x,int fa)
{
	dep[x]=dep[fa]+1;
	size[x]=1;
	fath[x]=fa;
	son[x]=-1;
	int max_size=0;
	for(int i=Last[x];i;i=Next[i])
	{
		int y=End[i];
		if(y!=fa)
		{
			dfs1(y,x);
			size[x]+=size[y];
			if(size[y]>max_size)
			{
				max_size=size[y];
				son[x]=y;
			}
		}
	}
}
int top[V],id[V],old[V],t;
void dfs2(int x,int top_now)
{
	id[x]=++t;
	old[t]=x;
	top[x]=top_now;
	if(son[x]!=-1) dfs2(son[x],top_now);
	for(int i=Last[x];i;i=Next[i])
	{
		int y=End[i];
		if(y!=fath[x]&&y!=son[x]) dfs2(y,y);
	}
}
int w[V],sum[V<<2],Min[V<<2],Max[V<<2],lazy[V<<2];
inline void merge(int k)
{
	sum[k]=sum[k<<1]+sum[k<<1|1];
	Min[k]=min(Min[k<<1],Min[k<<1|1]);
	Max[k]=max(Max[k<<1],Max[k<<1|1]);
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		sum[k]=Min[k]=Max[k]=w[old[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	merge(k);
}
inline void Swap(int &x,int &y)
{
	x^=y,y^=x,x^=y;
}
inline void work(int k)
{
	sum[k]=-sum[k];
	Min[k]=-Min[k];
	Max[k]=-Max[k];
	swap(Min[k],Max[k]);
	lazy[k]^=1;
}
inline void push_down(int k)
{
	lazy[k]=0;
	work(k<<1);
	work(k<<1|1);
}
void change(int k,int l,int r,int p,int v)
{
	if(l==r)
	{
		sum[k]=Min[k]=Max[k]=v;
		return;
	}
	if(lazy[k]) push_down(k);
	int mid=(l+r)>>1;
	if(p<=mid) change(k<<1,l,mid,p,v);
	else change(k<<1|1,mid+1,r,p,v);
	merge(k);
}
void modify(int k,int l,int r,int p,int q)
{
	if(p<=l&&r<=q)
	{
		work(k);
		return;
	}
	if(lazy[k]) push_down(k);
	int mid=(l+r)>>1;
	if(p<=mid) modify(k<<1,l,mid,p,q);
	if(q>mid) modify(k<<1|1,mid+1,r,p,q);
	merge(k);
}
int query_sum(int k,int l,int r,int p,int q)
{
	if(p<=l&&r<=q) return sum[k];
	if(lazy[k]) push_down(k);
	int mid=(l+r)>>1,res=0;
	if(p<=mid) res+=query_sum(k<<1,l,mid,p,q);
	if(q>mid) res+=query_sum(k<<1|1,mid+1,r,p,q);
	return res;
}
int query_max(int k,int l,int r,int p,int q)
{
	if(p<=l&&r<=q) return Max[k];
	if(lazy[k]) push_down(k);
	int mid=(l+r)>>1,res=-1e9;
	if(p<=mid) res=max(res,query_max(k<<1,l,mid,p,q));
	if(q>mid) res=max(res,query_max(k<<1|1,mid+1,r,p,q));
	return res;
}
int query_min(int k,int l,int r,int p,int q)
{
	if(p<=l&&r<=q) return Min[k];
	if(lazy[k]) push_down(k);
	int mid=(l+r)>>1,res=1e9;
	if(p<=mid) res=min(res,query_min(k<<1,l,mid,p,q));
	if(q>mid) res=min(res,query_min(k<<1|1,mid+1,r,p,q));
	return res;
}
inline void modify(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) Swap(x,y);
		modify(1,1,n,id[top[x]],id[x]);
		x=fath[top[x]];
	}
	if(x==y) return;
	if(dep[x]>dep[y]) Swap(x,y);
	modify(1,1,n,id[x]+1,id[y]);
}
inline void query_sum(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) Swap(x,y);
		ans+=query_sum(1,1,n,id[top[x]],id[x]);
		x=fath[top[x]];
	}
	if(x!=y)
	{
		if(dep[x]>dep[y]) Swap(x,y);
		ans+=query_sum(1,1,n,id[x]+1,id[y]);
	}
	printf("%d\n",ans);
}
inline void query_max(int x,int y)
{
	int ans=-1e9;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) Swap(x,y);
		ans=max(ans,query_max(1,1,n,id[top[x]],id[x]));
		x=fath[top[x]];
	}
	if(x!=y)
	{
		if(dep[x]>dep[y]) Swap(x,y);
		ans=max(ans,query_max(1,1,n,id[x]+1,id[y]));
	}
	printf("%d\n",ans);
}
inline void query_min(int x,int y)
{
	int ans=1e9;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) Swap(x,y);
		ans=min(ans,query_min(1,1,n,id[top[x]],id[x]));
		x=fath[top[x]];
	}
	if(x!=y)
	{
		if(dep[x]>dep[y]) Swap(x,y);
		ans=min(ans,query_min(1,1,n,id[x]+1,id[y]));
	}
	printf("%d\n",ans);
}
int main()
{
	n=read_int();
	for(int i=1;i<n;++i)
	{
		int u=read_int()+1,v=read_int()+1,w=read_int();
		add_edge(u,v,w);
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<n;++i)
	{
		int x=End[i<<1],y=End[i<<1|1];
		if(fath[y]==x) Swap(x,y);
		w[x]=Len[i<<1];
	}
	build(1,1,n);
	m=read_int();
	for(int i=1;i<=m;++i)
	{
		static char op[5];
		read_string(op);
		if(op[0]=='C')
		{
			int k=read_int(),w=read_int();
			int x=End[k<<1],y=End[k<<1|1];
			if(fath[y]==x) Swap(x,y);
			change(1,1,n,id[x],w);
		}
		else
		{
			int u=read_int()+1,v=read_int()+1;
			if(op[0]=='N') modify(u,v);
			else if(op[0]=='S') query_sum(u,v);
			else if(op[1]=='A') query_max(u,v);
			else query_min(u,v);
		}
	}
	return 0;
}