Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,q;

#define MAXN 100010

#define INF 0x3f3f3f3f

struct node

{

	int c[2],fa,sum,maxv,minv,val;

	bool neg,rev;

	node(){c[0] = c[1] = fa = val = 0;maxv = -INF;minv = INF;neg = rev = false;}

}t[MAXN << 1];

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void maintain(int rt)

{

	t[rt].sum = 0;t[rt].maxv = -INF;t[rt].minv = INF;

	if(rt > n)t[rt].sum = t[rt].maxv = t[rt].minv = t[rt].val;

	if(t[rt].c[0] != 0)

	{

		t[rt].sum += t[t[rt].c[0]].sum;

		t[rt].maxv = max(t[rt].maxv,t[t[rt].c[0]].maxv);

		t[rt].minv = min(t[rt].minv,t[t[rt].c[0]].minv);

	}

	if(t[rt].c[1] != 0)

	{

		t[rt].sum += t[t[rt].c[1]].sum;

		t[rt].maxv = max(t[rt].maxv,t[t[rt].c[1]].maxv);

		t[rt].minv = min(t[rt].minv,t[t[rt].c[1]].minv);

	}

	return;

}

void getneg(int k)

{

	t[k].maxv = -t[k].maxv;t[k].minv = -t[k].minv;

	swap(t[k].maxv,t[k].minv);

	t[k].sum = -t[k].sum;t[k].val = -t[k].val;

	t[k].neg ^= 1;

	return;

}

void pushdown(int rt)

{

	if(t[rt].neg)

	{

		getneg(t[rt].c[0]);getneg(t[rt].c[1]);

		t[rt].neg = false;		

	}

	if(t[rt].rev)

	{

		t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

		swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

	}

	return;

}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

stack<int> s;

void splay(int x)

{

	s.push(x);

	for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

void acc(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

void mrt(int k){acc(k);splay(k);t[k].rev ^= 1;return;}

void lin(int x,int y){mrt(x);t[x].fa = y;return;}



int main()

{

	scanf("%d",&n);

	int a,b,c;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		t[i + n].val = t[i + n].sum = c;maintain(i + n);

		++a;++b;

		lin(i + n,a);lin(i + n,b);

	}

	char ch[10];

	scanf("%d",&q);

	for(int i = 1;i <= q;++i)

	{

		scanf("%s%d%d",ch,&a,&b);

		if(ch[0] == 'C')

		{

			splay(n + a);

			t[n + a].val = b;

			maintain(n + a);

		}

		if(ch[0] == 'N')

		{

			++a;++b;

			mrt(a);acc(b);splay(b);

			getneg(b);

		}

		if(ch[0] == 'S')

		{

			++a;++b;

			mrt(a);acc(b);splay(b);

			printf("%d\n",t[b].sum);

		}

		if(ch[0] == 'M' && ch[1] == 'A')

		{

			++a;++b;

			mrt(a);acc(b);splay(b);

			printf("%d\n",t[b].maxv);

		}

		if(ch[0] == 'M' && ch[1] == 'I')

		{

			++a;++b;

			mrt(a);acc(b);splay(b);

			printf("%d\n",t[b].minv);

		}

	}

	return 0;

}