倒数第二个测试点

# include <iostream>
# include <cstdio>

using namespace std;

typedef long long ll;

const int N = 2e6 + 5;
const int inf = 1e13;

typedef struct {
	int x , y , next;
}Edge;
Edge edge[N];

int E = 0 , elast[N];

void add(int x , int y ) {
	E ++;
	edge[E].x = x;
	edge[E].y = y;
	edge[E].next = elast[x];
	elast[x] = E;
}

int f[N] , dep[N] , son[N] , siz[N];

void dfs1(int x , int fa) {
	dep[x] = dep[fa] + 1;
	f[x] = fa;
	siz[x] = 1;
	int maxv = -1;
	for (int i = elast[x] ; i ; i = edge[i].next) {
		int y = edge[i].y;
		if (y != fa) {
			dfs1(y , x);
			siz[x] += siz[y];
			if (siz[y] > maxv) son[x] = y , maxv = siz[y];
		}
	}
}

int top[N] , id[N] , w[N] , W[N] , Cnt = 0;

int n , m , x , y , z;

void dfs2(int x , int Top) {
	id[x] = ++ Cnt;
	w[Cnt] = W[x];
	top[x] = Top;
	if (!son[x]) return ;
	dfs2(son[x] , Top);
	for (int i = elast[x] ; i ; i = edge[i].next) {
		int y = edge[i].y;
		if (y != f[x] && y != son[x]) dfs2(y , y);
	}
}

typedef struct {
	int l , r , lazy , maxv , minv , sum;
}Node;
Node tr[N * 4];

void pushup(int p) {
	tr[p].minv = min(tr[p << 1].minv , tr[p << 1 | 1].minv);
	tr[p].maxv = max(tr[p << 1].maxv , tr[p << 1 | 1].maxv);
	tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
}

void pushdown(int p) {
	if (tr[p].lazy) {
		tr[p].lazy ^= 1;
		tr[p << 1].lazy ^= 1;
		tr[p << 1 | 1].lazy ^= 1;
		tr[p << 1].sum = -tr[p << 1].sum;
		tr[p << 1].minv = -tr[p << 1].minv;
		tr[p << 1].maxv = -tr[p << 1].maxv;
		tr[p << 1 | 1].sum = -tr[p << 1 | 1].sum;
		tr[p << 1 | 1].minv = -tr[p << 1 | 1].minv;
		tr[p << 1 | 1].maxv = -tr[p << 1 | 1].maxv;
		swap(tr[p << 1].minv , tr[p << 1].maxv);
		swap(tr[p << 1 | 1].minv , tr[p << 1 | 1].maxv);
	}
} 

void build(int p , int x , int y) {
	tr[p].l = x;
	tr[p].r = y;
	if (x == y) {
		tr[p].minv = tr[p].maxv = tr[p].sum = w[x];
		return ;
	} else {
		int mid = (x + y) >> 1;
		build(p << 1 , x , mid) , build(p << 1 | 1 , mid + 1 , y);
		pushup(p);
	}
}

void change(int p , int x , int d) {
	if (tr[p].l == tr[p].r) {
		tr[p].sum = tr[p].maxv = tr[p].minv = d;
		return ;
	} else {
		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1;
		if (x <= mid) change(p << 1 , x , d);
		else change(p << 1 | 1 , x , d);
		pushup(p);
	}
}

void modify(int p , int x , int y) {
	if (x <= tr[p].l && tr[p].r <= y) {
		tr[p].lazy ^= 1;
		tr[p].sum = -tr[p].sum;
		tr[p].maxv = -tr[p].maxv;
		tr[p].minv = -tr[p].minv;
		swap(tr[p].minv , tr[p].maxv);
		return ;
	} else {
		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1;
		if (x <= mid) modify(p << 1 , x , y);
		if (y > mid) modify(p << 1 | 1 , x , y);
		pushup(p);
	}
}

int get_sum(int p , int x , int y) {
	if (x <= tr[p].l && tr[p].r <= y) return tr[p].sum;
	else {
		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1 , ans = 0;
		if (x <= mid) ans += get_sum(p << 1 , x , y);
		if (y > mid) ans += get_sum(p << 1 | 1 , x , y);
		return ans; 
	}
}

int get_min(int p , int x , int y) {
	if (x <= tr[p].l && tr[p].r <= y) return tr[p].minv;
	else {
		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1 , ans = inf;
		if (x <= mid) ans = min(ans , get_min(p << 1 , x , y));
		if (y > mid) ans = min(ans , get_min(p << 1 | 1 , x , y));
		return ans; 
	}
}

int get_max(int p , int x , int y) {
	if (x <= tr[p].l && tr[p].r <= y) return tr[p].maxv;
	else {
		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1 , ans = -inf;
		if (x <= mid) ans = max(ans , get_max(p << 1 , x , y));
		if (y > mid) ans = max(ans , get_max(p << 1 | 1 , x , y));
		return ans; 
	}
}

void update(int x , int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x , y);
		modify(1 , id[top[x]] , id[x]);
		x = f[top[x]];
	}
	if (dep[x] > dep[y]) swap(x , y);
	if (x != y) modify(1 , id[x] + 1 , id[y]);
}

int 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 += get_sum(1 , id[top[x]] , id[x]);
		x = f[top[x]];
	}
	if (dep[x] > dep[y]) swap(x , y);
	if (x != y) ans += get_sum(1 , id[x] + 1 , id[y]);
	return ans;
}

int query_min(int x , int y) {
	int ans = inf;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x , y);
		ans = min(ans , get_min(1 , id[top[x]] , id[x]));
		x = f[top[x]];
	}
	if (dep[x] > dep[y]) swap(x , y);
	if (x != y) ans = min(ans , get_min(1 , id[x] + 1 , id[y]));
	return ans;
}

int query_max(int x , int y) {
	int ans = -inf;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x , y);
		ans = max(ans , get_max(1 , id[top[x]] , id[x]));
		x = f[top[x]];
	}
	if (dep[x] > dep[y]) swap(x , y);
	if (x != y) ans = max(ans , get_max(1 , id[x] + 1 , id[y]));
	return ans;
}

int Ver[N] , ver[N];
int main() {
	cin >> n;
	for (int i = 1 ; i <= n - 1 ; i ++) {
		scanf("%d%d%d" , &x , &y , &z);
		x ++ , y ++;
		add(x , y);
		add(y , x);
		W[y] = z;
		Ver[i] = x;
		ver[i] = y;
	}
	cin >> m;
	dfs1(1 , 0);
	dfs2(1 , 1);
	build(1 , 1 , n);
	while (m --) {
		char s[3];
		scanf("%s" , &s);
		if (s[0] == 'C') {
			scanf("%d%d" , &x , &y);
			if (dep[Ver[x]] > dep[ver[x]]) change(1 , id[Ver[x]] , y);
			else change(1 , id[ver[x]] , y);
			
		}
		if (s[0] == 'N') {
			scanf("%d%d" , &x , &y);
			x ++ , y ++;
			update(x , y);
		}
		if (s[0] == 'S') {
			scanf("%d%d" , &x , &y);
			x ++ , y ++;
			printf("%d\n" , query_sum(x , y));
		}
		if (s[0] == 'M' && s[1] == 'A') {
			scanf("%d%d" , &x , &y);
			x ++ , y ++;
			printf("%d\n" , query_max(x , y));
		}
		if (s[0] == 'M' && s[1] == 'I') {
			scanf("%d%d" , &x , &y);
			x ++ , y ++;
			printf("%d\n" , query_min(x , y));
		}
	}
	return 0;
}