Spoj QTREE HLD on edges

#include<bits/stdc++.h>
using namespace std;

const int sz = 10000;
const int lgsz = 15;

vector<int> g[sz];

struct segment_tree {
  vector<int> t;
  int n;
  segment_tree(int n) {
    this->n = n;
    t.assign(n * 4, 0);
  }
  void upd(int v, int tl, int tr, int i, int val) {
    if(tl + 1 == tr) {
      t[v] = val;
    } else {
      int tm = (tl + tr) / 2;
      if(i < tm) {
        upd(v * 2 + 1, tl, tm, i, val);
      } else {
        upd(v * 2 + 2, tm, tr, i, val);
      }
      t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    }
  }
  int get(int v, int tl, int tr, int l, int r) {
    if(tl >= r || tr <= l) return 0;
    if(tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return max(
      get(v * 2 + 1, tl, tm, l, r),
      get(v * 2 + 2, tm, tr, l, r)
    );
  }
};


int tsize[sz];
int par[sz][lgsz];
int depth[sz];

void dfs(int f, int p, int h = 0) {
  tsize[f] = 1;
  par[f][0] = p;
  depth[f] = h;
  for(int h=1;h<lgsz;h++) {
    par[f][h] = par[par[f][h-1]][h-1];
  }
  for(int v : g[f]) {
    if(v != p) {
      dfs(v, f, h + 1);
      tsize[f] +=  tsize[v];
    }
  }
}

void buildHLD(int f, int p, int c, vector<vector<int> > & hld) {
  bool used = false;
  for(int v : g[f]) {
    if(v == p) continue;
    if(tsize[v] > tsize[f] / 2) {
      used = true;
      if(c) {
        hld.back().push_back(v);
        buildHLD(v, f, 1, hld);
      } else {
        hld.push_back({f, v});
        buildHLD(v, f, 1, hld);
      }
      break;
    }
  }
  if(!used) {
    hld.push_back({f});
  }
  for(int v : g[f]) {
    if(v == p) continue;
    if(tsize[v] <= tsize[f] / 2) {
      buildHLD(v, f, 0, hld);
    }
  }
}

int inhld[sz];
int ind[sz];

int lca(int f, int t) {
  if(depth[f] < depth[t]) swap(f,t);
  for(int i=lgsz-1;i>=0;i--) {
    if(depth[par[f][i]] >= depth[t]) {
      f = par[f][i];
    }
  }
  if(f == t) return f;
  for(int i=lgsz-1;par[f][0] != par[t][0];i--) {
    if(par[f][i] != par[t][i]) {
      f = par[f][i];
      t = par[t][i];
    }
  }
  return par[f][0];
}

struct HLD {
  vector<int> head;
  vector<segment_tree> hld;
  int n;
  HLD(vector<vector<int> > & hways) {
    this -> n = hways.size();
    for(int i=0;i<n;i++) {
      hld.emplace_back((int)hways[i].size());
      head.push_back(hways[i][0]);
    }
  }
  void upd(int v, int value) {
    hld[inhld[v]].upd(0, 0, hld[inhld[v]].n, ind[v], value);
  }
  int get(int f, int t) {
    int u = lca(f, t);
    int ans = 0;
    while(inhld[f] != inhld[u]) {
      ans = max(ans, hld[inhld[f]].get(0, 0, hld[inhld[f]].n, 0, ind[f] + 1));
      f = par[head[inhld[f]]][0];
    }
    while(inhld[t] != inhld[u]) {
      ans = max(ans, hld[inhld[t]].get(0, 0, hld[inhld[t]].n, 0, ind[t] + 1));
      t = par[head[inhld[t]]][0];
    }
    if(depth[f] < depth[t]) swap(f, t);
    ans = max(ans, hld[inhld[f]].get(0, 0, hld[inhld[f]].n, ind[t] + 1, ind[f]+ 1));
    return ans;
  }
};

void solve() {
  int n;
  cin >> n;
  for(int i=0;i<n;i++) { g[i].clear(); }
  vector<pair<int,int> > edges;
  vector<int> w;
  for(int i=0;i<n - 1;i++) {
    int f, t, curw;
    cin >> f >> t >> curw;
    f--,t--;
    edges.push_back(make_pair(f,t));
    g[f].push_back(t);
    g[t].push_back(f);
    w.push_back(curw);
  }
  dfs(0, 0);
  vector<int> etov(n - 1);
  for(int i=0;i<n-1;i++) {
    int f = edges[i].first;
    int t = edges[i].second;
    if(par[f][0] == t) {
      etov[i] = f;
    } else {
      etov[i] = t;
    }
  }
  vector<vector<int> > hways;
  buildHLD(0, 0, 0, hways);
  for(int i=0;i<hways.size();i++) {
    for(int j=0;j<hways[i].size();j++) {
      inhld[hways[i][j]] = i;
      ind[hways[i][j]] = j;
    }
  }
  HLD hld (hways);
  for(int i=0;i<n-1;i++) {
    hld.upd(etov[i], w[i]);
  }
  string t;
  cin >> t;
  while(t != "DONE") {
    if(t == "QUERY") {
      int u, v;
      cin >> u >> v;
      u--,v--;
      cout << hld.get(u, v) << "\n";
    } else {
      int i, val;
      cin >> i >> val;
      i--;
      hld.upd(etov[i], val);
    }
    cin >> t;
  }
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t--) {
    solve();
  }
  return 0;
}