Code

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100005;
struct egde{
	int a, b, c;
}e[N];
struct Edge{
	int e, to, nxt;
}g[N << 1];
int h[N], idx;
int dfn[N], vis_cnt;
int big_son[N], siz[N], top[N], dep[N], father[N];
int w[N << 2], num[N], n;
void add(int a,int b,int c)
{
	g[++idx] = {c, b, h[a]}, h[a] = idx;
}
inline void pushup(int u)
{
	w[u] = max(w[u * 2], w[u * 2 + 1]);
}
void dfs1(int u,int fa)
{
	father[u] = fa;
	dfn[u] = ++vis_cnt;
	siz[u] = 1;
	for (int i = h[u]; i; i = g[i].nxt)
	{
		int j = g[i].to;
		if (j == fa)
			continue;
		dep[j] = dep[u] + 1;
		dfs1(j, u);
		siz[u] += siz[j];
		if (siz[j] > siz[big_son[u]])
			big_son[u] = j;
		num[dfn[j]] = g[i].e;
	}
}
void dfs2(int u,int fa,int Top)
{
	top[u] = Top;
	if (big_son[u])
		dfs2(big_son[u], u, Top);
	for (int i = h[u]; i; i = g[i].nxt)
	{
		int j = g[i].to;
		if (j == fa || j == big_son[u])
			continue;
		dfs2(j, u, j);
	}
}
void build(int u,int l,int r)
{
	if (l == r)
	{
		w[u] = num[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
	pushup(u);
}
void update(int u,int l,int r,int x,int v)
{
	if (l == r)
	{
		w[u] = v;
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid)
		update(u * 2, l, mid, x, v);
	else
		update(u * 2 + 1, mid + 1, r, x, v);
	pushup(u);
}
int query1(int u,int l,int r,int L,int R)
{
	if (L <= l && r <= R)
		return w[u];
	if (r < L || R < l)
		return 0;
	int mid = (l + r) >> 1;
	return max(query1(u * 2, l, mid, L, R), query1(u * 2 + 1, mid + 1, r, L, R));
}
int query2(int x,int y)
{
	int ans = 0;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		ans = max(ans, query1(1, 1, n, dfn[top[x]], dfn[x]));
		x = father[top[x]];
	}
	if (x != y)
		ans = max(ans, query1(1, 1, n, min(dfn[x], dfn[y]) + 1, max(dfn[x], dfn[y])));
	return ans;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;i++)
	{
		int a, b, c;
		scanf("%d%d%d",&a,&b,&c);
		add(a, b, c);
		add(b, a, c);
		e[i] = {a, b, c};
	}	
	dfs1(1, 1);
	dfs2(1, 1, 1);
	build(1, 1, n);
	for (;;)
	{
		char op[10];
		scanf("%s", op);
		if (op[0] == 'D')
			return 0;
		int x, y;
		scanf("%d%d",&x,&y);
		if (op[0] == 'C')
		{
			int a = e[x].a, b = e[x].b;
			if (father[b] == a)
				a = b;
			update(1, 1, n, dfn[a], y);
		}
		else
			printf("%d\n", query2(x, y));
	}
	return 0;
}