A.cpp

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
int read()
{
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	return x * f;
}
#define x first
#define y second
#define mp make_pair
const int maxn = 1e5 + 10, maxm = maxn << 1;
int e, tot1, tot2, n, m;
int to[maxm], nxt[maxm], head[maxn], dep[maxn], First[maxn], dfn[maxn], End[maxn], idfn[maxn], col[maxn];
pair<int, int> st[maxn << 2][24], now;
pair<pair<int, int>, int> E[maxn];

void add(int x, int y)
{
	to[++e] = y; nxt[e] = head[x]; head[x] = e;
	to[++e] = x; nxt[e] = head[y]; head[y] = e;
}
void dfs(int u, int fa)
{
	dfn[u] = ++tot1; idfn[tot1] = u; First[u] = ++tot2; dep[u] = dep[fa] + 1;
	st[tot2][0] = make_pair(dep[u], u);
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs(v, u);
		st[++tot2][0] = make_pair(dep[u], u);
	}
	End[u] = tot1;
}
int Log[maxn << 2];
void RMQ()
{
	for(int i = 2; i <= tot2; ++i) Log[i] = Log[i >> 1] + 1;
	for(int i = 1; i <= Log[tot2]; ++i)
		for(int j = 1; j + (1 << i) - 1 <= tot2; ++j)
/**/		st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
int Lca(int x, int y)
{
	x = First[x]; y = First[y];
	if(x > y) swap(x, y);
	return min(st[x][Log[y - x + 1]], st[y - (1 << Log[y - x + 1]) + 1][Log[y - x + 1]]).second;
}

namespace BIT
{
	LL c[maxn];
	int lowbit(int x) { return x & (-x); }
	void upt(int x, int v) { while(x <= n) c[x] += v, x += lowbit(x); }
	LL que(int x) { LL r = 0; while(x) { r += c[x]; x -= lowbit(x); } return r; }
}

LL dist(int x, int y)
{
	if(y == -1 && x == -1) return -1;
	if(x == -1 || y == -1) return 0;
	int tmp = Lca(x, y);
	return BIT::que(dfn[x]) + BIT::que(dfn[y]) - 2 * BIT::que(dfn[tmp]);
}
#define ls o << 1, l, mid
#define rs o << 1 | 1, mid + 1, r
namespace SGT
{
	pair<int, int> t[maxn << 2];
	pair<int, int> merge(const pair<int, int> &a, const pair<int, int> &b)
	{
		pair<LL, pair<int, int> > tmp1 = make_pair(dist(a.first, a.second), make_pair(a.first, a.second));
		pair<LL, pair<int, int> > tmp2 = make_pair(dist(a.first, b.second), make_pair(a.first, b.second));
		pair<LL, pair<int, int> > tmp3 = make_pair(dist(b.first, a.second), make_pair(b.first, a.second));
		pair<LL, pair<int, int> > tmp4 = make_pair(dist(b.first, b.second), make_pair(b.first, b.second));
		pair<LL, pair<int, int> > tmp5 = make_pair(dist(b.first, a.first), make_pair(b.first, a.first));
		pair<LL, pair<int, int> > tmp6 = make_pair(dist(a.second, b.second), make_pair(a.second, b.second));
		return max(tmp1, max(tmp2, max(tmp3, max(tmp4, max(tmp5, tmp6))))).second;
	}
	void build(int o, int l, int r)
	{
		t[o].first = t[o].second = -1;
		if(l == r)
		{
			t[o].first = idfn[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(ls); build(rs);
		t[o] = merge(t[o << 1], t[o << 1 | 1]);
	}
	void upt(int o, int l, int r, int x, int y)
	{
		/*
		if(l == r)
		{
			t[o].first = t[o].second = -1;
			if(fg) t[o].first = idfn[l];
			return ;
		}*/
		if(x <= l && r <= y) return ;
		int mid = (l + r) >> 1;
		if(x <= mid) upt(ls, x, y);
		else upt(rs, x, y);
		t[o] = merge(t[o << 1], t[o << 1 | 1]);
	}
	/*
	void que(int o, int l, int r, int x, int y)
	{
		if(x <= l && r <= y) 
		{
			now = merge(now, t[o]);
			return ;
		}
		int mid = (l + r) >> 1;
		if(x <= mid) que(ls, x, y);
		if(y > mid) que(rs, x, y);
	}*/
}	
char A[3];
int main()
{
	n = read();
	for(int i = 1; i < n; ++i)
	{
		int x = read(), y = read(), z = read();
		add(x, y); E[i] = mp(mp(x, y), z);
	}
	dfs(1, 0);
	RMQ(); 
	for(int i = 1; i < n; ++i)
	{
		int &x = E[i].x.x, &y = E[i].x.y;
		if(dep[x] < dep[y]) swap(x, y);
		BIT::upt(dfn[x], E[i].y); BIT::upt(End[x] + 1, -E[i].y);
	}
	SGT::build(1, 1, tot1);
	m = read();
	/*
	for(int i = 1; i <= m; ++i)
	{
		char A[3]; int x;
		scanf("%s", A); x = read();
		if(A[0] == 'C')
		{
			col[x] ^= 1;
			if(col[x] == 0) SGT::upt(1, 1, tot1, dfn[x], 1);
			else SGT::upt(1, 1, tot1, dfn[x], 0);
		}
		else 
		{
			now = make_pair(-1, -1);
			SGT::que(1, 1, tot1, dfn[x], End[x]);
			printf("%d\n", dist(now.first, now.second));
		}
	}*/

	using namespace SGT;
	while(m--)
	{
		scanf("%s", A);
		if(A[0] == 'Q')
		{
			int x = read();
			int u = t[1].x, v = t[1].y;
			//if(dist(u, x) > dist(v, x)) printf("%d\n", u);
			//else printf();
			printf("%lld\n", max(dist(u, x), dist(v, x)));
		}
		else
		{
			int x = read(), y = read();
			int tmp = y - E[x].y; E[x].y = y;
			BIT::upt(dfn[E[x].x.x], tmp); BIT::upt(End[E[x].x.x] + 1, -tmp);
			SGT::upt(1, 1, tot1, dfn[E[x].x.x], End[E[x].x.x]);
		}
	}

	return 0;
}