RT link

#include<bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define v first
#define w second
#define mp(x,y) make_pair(x,y)

namespace FastIO
{
	#define getch getchar
	inline int input()
	{
		int num = 0,f = 1;
		char ch = getch();
		while(ch < '0' || ch > '9')
		{
			if(ch == '-') f = -1;
			ch = getch();
		}
		while(ch >= '0' && ch <= '9')
		{
			num = (num << 1) + (num << 3) + (ch ^ 48);
			ch = getch();
		}
		return num * f;
	}
	
	inline void printNum(int num)
	{
		if(num >= 10) printNum(num / 10);
		putchar(num % 10 + 48);
	}
	
	inline void print(int num,char ch = ' ')
	{
		if(num < 0) putchar('-'),num = -num;
		printNum(num);
		putchar(ch);
	}
	#undef getch
}
using FastIO::input;
using FastIO::print;

const int N = 1e5 + 5;
const int INF = -1u / 2;
struct Edge {int u,v,w;};
struct SegmentTree
{
	struct Node
	{
		int l,r,val,add,cov;
		#define l(x) tree[x].l
		#define r(x) tree[x].r
		#define val(x) tree[x].val
		#define add(x) tree[x].add
		#define cov(x) tree[x].cov
		#define ave(x) (tree[x].l + tree[x].r >> 1)
	};
	#define mid (l + r >> 1)
	Node tree[N << 2];
	
	void build(int l,int r,int pos,int (&arr)[N])
	{
		l(pos) = l,r(pos) = r,cov(pos) = -INF;
		if(l == r)
		{
			val(pos) = arr[l];
			return;
		}
		build(l,mid,pos << 1,arr);
		build(mid + 1,r,pos << 1 | 1,arr);
		val(pos) = max(val(pos << 1),val(pos << 1 | 1));
	}
	
	void update(int pos,int Add,int Cov)
	{
		if(Cov != -INF) val(pos) = cov(pos) = Cov,add(pos) = 0;
		val(pos) += Add,add(pos) += Add;
	}
	
	void spread(int pos)
	{
		update(pos << 1,add(pos),cov(pos));
		update(pos << 1 | 1,add(pos),cov(pos));
		cov(pos) = -INF,add(pos) = 0;
	}
	
	void increase(int l,int r,int k,int pos)
	{
		if(l <= l(pos) && r(pos) <= r)
		{
			add(pos) += k,val(pos) += k;
			return;
		}
		spread(pos);
		if(l <= ave(pos)) increase(l,r,k,pos << 1);
		if(r > ave(pos)) increase(l,r,k,pos << 1 | 1);
		val(pos) = max(val(pos << 1),val(pos << 1 | 1));
	}
	
	void cover(int l,int r,int k,int pos)
	{
		if(l <= l(pos) && r(pos) <= r)
		{
			val(pos) = cov(pos) = k;
			return;
		}
		spread(pos);
		if(l <= ave(pos)) cover(l,r,k,pos << 1);
		if(r > ave(pos)) cover(l,r,k,pos << 1 | 1);
		val(pos) = max(val(pos << 1),val(pos << 1 | 1));
	}
	
	int query(int l,int r,int pos)
	{
		if(l <= l(pos) && r(pos) <= r)
			return val(pos);
		spread(pos);
		int res = -INF;
		if(l <= ave(pos)) res = max(res,query(l,r,pos << 1));
		if(r > ave(pos)) res = max(res,query(l,r,pos << 1 | 1));
		return res;
	}
	
	#undef l
	#undef r
	#undef val	
	#undef add
	#undef cov	
	#undef ave
	#undef mid	
};
int n,ts;
string s;
SegmentTree ST;
int fa[N],son[N],ext[N],dep[N],top[N],dfn[N],w[N];
vector <Edge> vec;
vector <pii> edge[N];

void getSon(int u,int from,int depth)
{
	fa[u] = from,dep[u] = depth,ext[u] = 1;
	
	for(auto tmp : edge[u])
	{
		int v = tmp.v;
		if(v == from) continue;
		getSon(v,u,depth + 1);
		ext[u] += ext[v];
		if(ext[v] > ext[son[u]]) son[u] = v;
	}
}

void getDfn(int u,int apex)
{
	dfn[u] = ++ts,top[u] = apex;
	
	if(!son[u]) return;
	getDfn(son[u],apex);
	
	for(auto tmp : edge[u])
	{
		int v = tmp.v;
		if(v != fa[u] && v != son[u])
			getDfn(v,v);
	}
}

void getWorth(int u,int worth)
{
	w[dfn[u]] = worth;
	for(auto tmp : edge[u])
	{
		int v = tmp.v;
		if(v != fa[u])
			getWorth(v,tmp.w);
	}
}

void change(int k,int w)
{
	int u = vec[k - 1].u,v = vec[k - 1].v;
	if(dfn[u] < dfn[v]) swap(u,v);
	ST.cover(dfn[u],dfn[u],w,1);
}

void cover(int u,int v,int k)
{
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]])
			swap(u,v);
		ST.cover(dfn[top[u]],dfn[u],k,1);
		u = fa[top[u]];
	}
	if(dfn[u] < dfn[v]) swap(u,v);
	ST.cover(dfn[v] + 1,dfn[u],k,1);
}

void add(int u,int v,int k)
{
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]])
			swap(u,v);
		ST.increase(dfn[top[u]],dfn[u],k,1);
		u = fa[top[u]];
	}
	if(dfn[u] < dfn[v]) swap(u,v);
	ST.increase(dfn[v] + 1,dfn[u],k,1);
}

int query(int u,int v)
{
	int ans = -INF;
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]])
			swap(u,v);
		ans = max(ans,ST.query(dfn[top[u]],dfn[u],1));
		u = fa[top[u]];
	}
	if(dfn[u] < dfn[v]) swap(u,v);
	ans = max(ans,ST.query(dfn[v] + 1,dfn[u],1));
	return ans;
}

int main()
{
//	freopen("tree.in","r",stdin);
//	freopen("my.out","w",stdout);
	n = input();
	for(int i = 1;i < n;i++)
	{
		int u = input(),v = input(),w = input();
		edge[u].push_back(mp(v,w)),
		edge[v].push_back(mp(u,w));
		vec.push_back({u,v,w});
	}
	getSon(1,0,1);
	getDfn(1,1);
	getWorth(1,0);
	ST.build(1,n,1,w);
	
//	for(int i = 1;i <= n;i++)
//		print(ST.query(i,i,1));
//	puts("");
	
	while(cin >> s)
	{
		if(s == "Stop") break;
		int u = input(),v = input();
		if(s == "Change")
			change(u,v);
		if(s == "Cover")
			cover(u,v,input());
		if(s == "Add") 
			add(u,v,input());
		if(s == "Max") 
			print(query(u,v),'\n');
	}
}