//Shreyans Sheth [bholagabbar]
#include <bits/stdc++.h>
using namespace std;
#define readFile freopen("E:/Shreyans/Documents/Coding Workspace/STDINPUT.txt","v",stdin);
#define getPrecision(s,p) fixed<<setprecision(p)<<s
#define boostIO ios_base::sync_with_stdio(0), cin.tie(0)
#define CLR(s) memset(&s, 0, sizeof s)
#define hashset unordered_set
#define hashmap unordered_map
#define PI(x) printf("%d", x)
#define PL(x) printf("%ld", x)
#define SI(x) scanf("%d", &x)
#define SD(x) scanf("%lf", &x)
#define SL(x) scanf("%lld", &x)
#define pb push_back
#define mp make_pair
#define N 10001
#define LN 14
#define F first
#define S second
#define endl '\n'
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
vector<int> adj[N];
vector<int> edges[N];
vector<int> idx[N];
int subSize[N];
int depth[N];
int lca[LN][N];
int segTree[N<<2];
int pos;
int chainNo;
int chainHead[N];
int chainIndex[N];
int arr[N];
int basePos[N];
int endNode[N];
void Dfs(int node, int parent, int level) {
depth[node] = level;
lca[0][node] = parent;
subSize[node] = 1;
int x = adj[node].size();
while (x--) {
int next = adj[node][x];
if (next != parent){
endNode[idx[node][x]] = next;
Dfs(next, node, level+1);
subSize[node] += subSize[next];
}
}
}
void HLD(int node, int cost, int parent) {
if (chainHead[chainNo] == -1) {
chainHead[chainNo] = node;
}
pos++;
chainIndex[node] = chainNo;
basePos[node] = pos;
arr[pos] = cost;
int specialChild = -1, edgeCost = 0;
int x = adj[node].size();
while (x--) {
int next = adj[node][x];
if (next != parent) {
if (specialChild == -1 || subSize[next] > subSize[specialChild]) {
specialChild = next;
edgeCost = edges[node][x];
}
}
}
if (specialChild != -1) {
HLD(specialChild, edgeCost, node);
}
x = adj[node].size();
while (x--) {
int next = adj[node][x];
if (next != parent && next != specialChild) {
chainNo++;
HLD(next, edges[node][x], node);
}
}
}
void initializeLCA(int n) {
for (int j = 1; j < LN; j++) {
for (int i = 1; i <= n; i++) {
lca[j][i] = lca[j - 1][lca[j - 1][i]];
}
}
}
int LCA(int x, int y) {
if (depth[x] < depth[y]) {
std::swap(x, y);
}
for (int i = LN - 1; i >= 0; i--) {
if (depth[x] - (1 << i) >= depth[y]) {
x = lca[i][x];
}
}
if (x == y) {
return x;
}
for (int i = LN - 1; i >= 0; i--) {
if (lca[i][x] != lca[i][y]) {
x = lca[i][x];
y = lca[i][y];
}
}
return lca[0][x];
}
void buildSegTree(int node, int u, int v) {
if(u == v) {
segTree[node] = arr[u];
return ;
}
int mid = (u + v) >> 1;
int lc = node << 1;
int rc = lc | 1;
buildSegTree (lc, u, mid);
buildSegTree (rc, mid + 1, v);
segTree[node] = std::max(segTree[lc], segTree[rc]);
}
void updateSegTree(int node, int u, int v, int i, int val) {
if(u == v) {
segTree[node] = val;
return;
}
int mid = (u + v) >> 1;
int lc = node << 1;
int rc= lc | 1;
if(i <= mid) {
updateSegTree(lc, u, mid, i, val);
} else {
updateSegTree(rc, mid+ 1, v, i, val);
}
segTree[node]=std::max(segTree[lc], segTree[rc]);
}
int querySegTree(int node, int u, int v, int ql, int qr) {
if(ql > v || u > qr) {
return 0;
}
if(u >= ql && v <= qr) {
return segTree[node];
}
int mid = (u + v) >> 1;
int lc = node << 1;
int rc = lc | 1;
int lv = querySegTree(lc, u, mid, ql, qr);
int rv = querySegTree(rc, mid + 1, v, ql, qr);
return std::max(rv,lv);
}
int queryUp(int u,int v) {
if(u == v) {
return 0;
}
int lchain, rchain = chainIndex[v], ans = -1;
while (1) {
lchain = chainIndex[u];
if(lchain == rchain) {
if(u == v) {
break;
}
int currAns = querySegTree(1, 1, pos, basePos[v] + 1, basePos[u]);
ans = std::max(ans, currAns);
break;
}
int currAns = querySegTree(1, 1, pos, basePos[chainHead[lchain]], basePos[u]);
ans = std::max(ans, currAns);
u = chainHead[lchain];
u = lca[0][u];
}
return ans;
}
void Initialize(int n) {
for (int i = 0; i <= n; i++) {
adj[i].clear();
edges[i].clear();
idx[i].clear();
chainHead[i] = -1;
for (int j = 0; j < LN; j++) {
lca[j][i]=-1;
}
}
}
int queryPath(int u, int v) {
int lca = LCA(u, v);
int a = queryUp(u, lca);
int b = queryUp(v, lca);
return std::max(a, b);
}
void Update(int i, int val) {
int node = endNode[i];
updateSegTree(1, 1, pos, basePos[node], val);
}
int main() {
int t;
SI(t);
while (t--) {
int n;
SI(n);
Initialize(n);
for (int i=1;i<n;i++) {
int u, v, w;
SI(u), SI(v), SI(w);
adj[u].pb(v);
edges[u].pb(w);
idx[u].pb(i);
adj[v].pb(u);
edges[v].pb(w);
idx[v].pb(i);
}
Dfs(1, 0, 0);
initializeLCA(n);
pos = -1;
chainNo = 1;
HLD(1, 0, 0);
buildSegTree(1, 1,pos);
char str[10];
scanf("%s", str);
while (str[0] != 'D') {
int type, u ,v;
SI(u);
SI(v);
if (str[0] == 'Q') {
PI(queryPath(u, v));
printf("\n");
} else {
Update(u, v);
}
scanf("%s", str);
}
}
}
Ly9TaHJleWFucyBTaGV0aCBbYmhvbGFnYWJiYXJdCiAKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgcmVhZEZpbGUgZnJlb3BlbigiRTovU2hyZXlhbnMvRG9jdW1lbnRzL0NvZGluZyBXb3Jrc3BhY2UvU1RESU5QVVQudHh0IiwidiIsc3RkaW4pOwojZGVmaW5lIGdldFByZWNpc2lvbihzLHApIGZpeGVkPDxzZXRwcmVjaXNpb24ocCk8PHMKI2RlZmluZSBib29zdElPIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCksIGNpbi50aWUoMCkKI2RlZmluZSBDTFIocykgbWVtc2V0KCZzLCAwLCBzaXplb2YgcykKI2RlZmluZSBoYXNoc2V0IHVub3JkZXJlZF9zZXQKI2RlZmluZSBoYXNobWFwIHVub3JkZXJlZF9tYXAKI2RlZmluZSBQSSh4KSBwcmludGYoIiVkIiwgeCkKI2RlZmluZSBQTCh4KSBwcmludGYoIiVsZCIsIHgpCiNkZWZpbmUgU0koeCkgc2NhbmYoIiVkIiwgJngpCiNkZWZpbmUgU0QoeCkgc2NhbmYoIiVsZiIsICZ4KQojZGVmaW5lIFNMKHgpIHNjYW5mKCIlbGxkIiwgJngpCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgTiAxMDAwMQojZGVmaW5lIExOIDE0CiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgZW5kbCAnXG4nCiAKdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGxsLCBsbD4gcGxsOwoKdmVjdG9yPGludD4gYWRqW05dOwp2ZWN0b3I8aW50PiBlZGdlc1tOXTsKdmVjdG9yPGludD4gaWR4W05dOwogCmludCBzdWJTaXplW05dOwppbnQgZGVwdGhbTl07CiAKaW50IGxjYVtMTl1bTl07CiAKaW50IHNlZ1RyZWVbTjw8Ml07CiAKaW50IHBvczsKaW50IGNoYWluTm87CmludCBjaGFpbkhlYWRbTl07CmludCBjaGFpbkluZGV4W05dOwppbnQgYXJyW05dOwppbnQgYmFzZVBvc1tOXTsKaW50IGVuZE5vZGVbTl07CiAKdm9pZCBEZnMoaW50IG5vZGUsIGludCBwYXJlbnQsIGludCBsZXZlbCkgewogICAgZGVwdGhbbm9kZV0gPSBsZXZlbDsKICAgIGxjYVswXVtub2RlXSA9IHBhcmVudDsKICAgIHN1YlNpemVbbm9kZV0gPSAxOwogICAgaW50IHggPSBhZGpbbm9kZV0uc2l6ZSgpOwogICAgd2hpbGUgKHgtLSkgewogICAgICAgIGludCBuZXh0ID0gYWRqW25vZGVdW3hdOwogICAgICAgIGlmIChuZXh0ICE9IHBhcmVudCl7CiAgICAgICAgICAgIGVuZE5vZGVbaWR4W25vZGVdW3hdXSA9IG5leHQ7CiAgICAgICAgICAgIERmcyhuZXh0LCBub2RlLCBsZXZlbCsxKTsKICAgICAgICAgICAgc3ViU2l6ZVtub2RlXSArPSBzdWJTaXplW25leHRdOwogICAgICAgIH0KICAgIH0KfQogCnZvaWQgSExEKGludCBub2RlLCBpbnQgY29zdCwgaW50IHBhcmVudCkgewogICAgaWYgKGNoYWluSGVhZFtjaGFpbk5vXSA9PSAtMSkgewogICAgICAgIGNoYWluSGVhZFtjaGFpbk5vXSA9IG5vZGU7CiAgICB9CiAgICBwb3MrKzsKICAgIGNoYWluSW5kZXhbbm9kZV0gPSBjaGFpbk5vOwogICAgYmFzZVBvc1tub2RlXSA9IHBvczsKICAgIGFycltwb3NdID0gY29zdDsKICAgIGludCBzcGVjaWFsQ2hpbGQgPSAtMSwgZWRnZUNvc3QgPSAwOwogICAgaW50IHggPSBhZGpbbm9kZV0uc2l6ZSgpOwogICAgd2hpbGUgKHgtLSkgewogICAgICAgIGludCBuZXh0ID0gYWRqW25vZGVdW3hdOwogICAgICAgIGlmIChuZXh0ICE9IHBhcmVudCkgewogICAgICAgICAgICBpZiAoc3BlY2lhbENoaWxkID09IC0xIHx8IHN1YlNpemVbbmV4dF0gPiBzdWJTaXplW3NwZWNpYWxDaGlsZF0pIHsKICAgICAgICAgICAgICAgIHNwZWNpYWxDaGlsZCA9IG5leHQ7CiAgICAgICAgICAgICAgICBlZGdlQ29zdCA9IGVkZ2VzW25vZGVdW3hdOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgaWYgKHNwZWNpYWxDaGlsZCAhPSAtMSkgewogICAgICAgIEhMRChzcGVjaWFsQ2hpbGQsIGVkZ2VDb3N0LCBub2RlKTsKICAgIH0KICAgIHggPSBhZGpbbm9kZV0uc2l6ZSgpOwogICAgd2hpbGUgKHgtLSkgewogICAgICAgIGludCBuZXh0ID0gYWRqW25vZGVdW3hdOwogICAgICAgIGlmIChuZXh0ICE9IHBhcmVudCAmJiBuZXh0ICE9IHNwZWNpYWxDaGlsZCkgewogICAgICAgICAgICBjaGFpbk5vKys7CiAgICAgICAgICAgIEhMRChuZXh0LCBlZGdlc1tub2RlXVt4XSwgbm9kZSk7CiAgICAgICAgfQogICAgfQp9CiAKdm9pZCBpbml0aWFsaXplTENBKGludCBuKSB7CiAgICBmb3IgKGludCBqID0gMTsgaiA8IExOOyBqKyspIHsKICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICAgICAgbGNhW2pdW2ldID0gbGNhW2ogLSAxXVtsY2FbaiAtIDFdW2ldXTsKICAgICAgICB9CiAgICB9Cn0KIAppbnQgTENBKGludCB4LCBpbnQgeSkgewogICAgaWYgKGRlcHRoW3hdIDwgZGVwdGhbeV0pIHsKICAgICAgICBzdGQ6OnN3YXAoeCwgeSk7CiAgICB9CiAgICBmb3IgKGludCBpID0gTE4gLSAxOyBpID49IDA7IGktLSkgewogICAgICAgIGlmIChkZXB0aFt4XSAtICgxIDw8IGkpID49IGRlcHRoW3ldKSB7CiAgICAgICAgICAgIHggPSBsY2FbaV1beF07CiAgICAgICAgfQogICAgfQogICAgaWYgKHggPT0geSkgewogICAgICAgIHJldHVybiB4OwogICAgfQogICAgZm9yIChpbnQgaSA9IExOIC0gMTsgaSA+PSAwOyBpLS0pIHsKICAgICAgICBpZiAobGNhW2ldW3hdICE9IGxjYVtpXVt5XSkgewogICAgICAgICAgICB4ID0gbGNhW2ldW3hdOwogICAgICAgICAgICB5ID0gbGNhW2ldW3ldOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBsY2FbMF1beF07Cn0KCnZvaWQgYnVpbGRTZWdUcmVlKGludCBub2RlLCBpbnQgdSwgaW50IHYpIHsKICAgIGlmKHUgPT0gdikgewogICAgICAgIHNlZ1RyZWVbbm9kZV0gPSBhcnJbdV07CiAgICAgICAgcmV0dXJuIDsKICAgIH0KICAgIGludCBtaWQgPSAodSArIHYpID4+IDE7CiAgICBpbnQgbGMgPSBub2RlIDw8IDE7CiAgICBpbnQgcmMgPSBsYyB8IDE7CiAgICBidWlsZFNlZ1RyZWUgKGxjLCB1LCBtaWQpOwogICAgYnVpbGRTZWdUcmVlIChyYywgbWlkICsgMSwgdik7CiAgICBzZWdUcmVlW25vZGVdID0gc3RkOjptYXgoc2VnVHJlZVtsY10sIHNlZ1RyZWVbcmNdKTsKfQoKdm9pZCB1cGRhdGVTZWdUcmVlKGludCBub2RlLCBpbnQgdSwgaW50IHYsIGludCBpLCBpbnQgdmFsKSB7CiAgICBpZih1ID09IHYpIHsKICAgICAgICBzZWdUcmVlW25vZGVdID0gdmFsOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBtaWQgPSAodSArIHYpID4+IDE7CiAgICBpbnQgbGMgPSBub2RlIDw8IDE7CiAgICBpbnQgcmM9IGxjIHwgMTsKICAgIGlmKGkgPD0gbWlkKSB7CiAgICAgICAgdXBkYXRlU2VnVHJlZShsYywgdSwgbWlkLCBpLCB2YWwpOwogICAgfSBlbHNlIHsKICAgICAgICB1cGRhdGVTZWdUcmVlKHJjLCBtaWQrICAxLCB2LCBpLCB2YWwpOwogICAgfQogICAgc2VnVHJlZVtub2RlXT1zdGQ6Om1heChzZWdUcmVlW2xjXSwgc2VnVHJlZVtyY10pOwp9CgppbnQgcXVlcnlTZWdUcmVlKGludCBub2RlLCBpbnQgdSwgaW50IHYsIGludCBxbCwgaW50IHFyKSB7CiAgICBpZihxbCA+IHYgfHwgdSA+IHFyKSB7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CiAgICBpZih1ID49IHFsICYmIHYgPD0gcXIpIHsKICAgICAgICByZXR1cm4gc2VnVHJlZVtub2RlXTsKICAgIH0KICAgIGludCBtaWQgPSAodSArIHYpID4+IDE7CiAgICBpbnQgbGMgPSBub2RlIDw8IDE7CiAgICBpbnQgcmMgPSBsYyB8IDE7CiAgICBpbnQgbHYgPSBxdWVyeVNlZ1RyZWUobGMsIHUsIG1pZCwgcWwsIHFyKTsKICAgIGludCBydiA9IHF1ZXJ5U2VnVHJlZShyYywgbWlkICsgMSwgdiwgcWwsIHFyKTsKICAgIHJldHVybiBzdGQ6Om1heChydixsdik7Cn0KCmludCBxdWVyeVVwKGludCB1LGludCB2KSB7CiAgICBpZih1ID09IHYpIHsKICAgICAgICByZXR1cm4gMDsKICAgIH0KICAgIGludCBsY2hhaW4sIHJjaGFpbiA9IGNoYWluSW5kZXhbdl0sIGFucyA9IC0xOwogICAgd2hpbGUgKDEpIHsKICAgICAgICBsY2hhaW4gPSBjaGFpbkluZGV4W3VdOwogICAgICAgIGlmKGxjaGFpbiA9PSByY2hhaW4pIHsKICAgICAgICAgICAgaWYodSA9PSB2KSB7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICBpbnQgY3VyckFucyA9IHF1ZXJ5U2VnVHJlZSgxLCAxLCBwb3MsIGJhc2VQb3Nbdl0gKyAxLCBiYXNlUG9zW3VdKTsKICAgICAgICAgICAgYW5zID0gc3RkOjptYXgoYW5zLCBjdXJyQW5zKTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgICAgIGludCBjdXJyQW5zID0gcXVlcnlTZWdUcmVlKDEsIDEsIHBvcywgYmFzZVBvc1tjaGFpbkhlYWRbbGNoYWluXV0sIGJhc2VQb3NbdV0pOwogICAgICAgIGFucyA9IHN0ZDo6bWF4KGFucywgY3VyckFucyk7CiAgICAgICAgdSA9IGNoYWluSGVhZFtsY2hhaW5dOwogICAgICAgIHUgPSBsY2FbMF1bdV07CiAgICB9CiAgICByZXR1cm4gYW5zOwp9Cgp2b2lkIEluaXRpYWxpemUoaW50IG4pIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IG47IGkrKykgewogICAgICAgIGFkaltpXS5jbGVhcigpOwogICAgICAgIGVkZ2VzW2ldLmNsZWFyKCk7CiAgICAgICAgaWR4W2ldLmNsZWFyKCk7CiAgICAgICAgY2hhaW5IZWFkW2ldID0gLTE7CiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBMTjsgaisrKSB7CiAgICAgICAgICAgIGxjYVtqXVtpXT0tMTsKICAgICAgICB9CiAgICB9Cn0KCmludCBxdWVyeVBhdGgoaW50IHUsIGludCB2KSB7CiAgICBpbnQgbGNhID0gTENBKHUsIHYpOwogICAgaW50IGEgPSBxdWVyeVVwKHUsIGxjYSk7CiAgICBpbnQgYiA9IHF1ZXJ5VXAodiwgbGNhKTsKICAgIHJldHVybiBzdGQ6Om1heChhLCBiKTsKfQoKdm9pZCBVcGRhdGUoaW50IGksIGludCB2YWwpIHsKICAgIGludCBub2RlID0gZW5kTm9kZVtpXTsKICAgIHVwZGF0ZVNlZ1RyZWUoMSwgMSwgcG9zLCBiYXNlUG9zW25vZGVdLCB2YWwpOwp9CgppbnQgbWFpbigpIHsKICAgIGludCB0OwogICAgU0kodCk7CiAgICB3aGlsZSAodC0tKSB7CiAgICAgICAgaW50IG47CiAgICAgICAgU0kobik7CiAgICAgICAgSW5pdGlhbGl6ZShuKTsKICAgICAgICBmb3IgKGludCBpPTE7aTxuO2krKykgewogICAgICAgICAgICBpbnQgdSwgdiwgdzsKICAgICAgICAgICAgU0kodSksIFNJKHYpLCBTSSh3KTsKICAgICAgICAgICAgYWRqW3VdLnBiKHYpOwogICAgICAgICAgICBlZGdlc1t1XS5wYih3KTsKICAgICAgICAgICAgaWR4W3VdLnBiKGkpOwogICAgICAgICAgICBhZGpbdl0ucGIodSk7CiAgICAgICAgICAgIGVkZ2VzW3ZdLnBiKHcpOwogICAgICAgICAgICBpZHhbdl0ucGIoaSk7CiAgICAgICAgfQogICAgICAgIERmcygxLCAwLCAwKTsKICAgICAgICBpbml0aWFsaXplTENBKG4pOwogICAgICAgIHBvcyA9IC0xOwogICAgICAgIGNoYWluTm8gPSAxOwogICAgICAgIEhMRCgxLCAwLCAwKTsKICAgICAgICBidWlsZFNlZ1RyZWUoMSwgMSxwb3MpOwogICAgICAgIGNoYXIgc3RyWzEwXTsKICAgICAgICBzY2FuZigiJXMiLCBzdHIpOwogICAgICAgIHdoaWxlIChzdHJbMF0gIT0gJ0QnKSB7CiAgICAgICAgICAgIGludCB0eXBlLCB1ICx2OwogICAgICAgICAgICBTSSh1KTsKICAgICAgICAgICAgU0kodik7CiAgICAgICAgICAgIGlmIChzdHJbMF0gPT0gJ1EnKSB7CiAgICAgICAgICAgICAgICBQSShxdWVyeVBhdGgodSwgdikpOwogICAgICAgICAgICAgICAgcHJpbnRmKCJcbiIpOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgVXBkYXRlKHUsIHYpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHNjYW5mKCIlcyIsIHN0cik7CiAgICAgICAgfQogICAgfQp9