蒟蒻初学树链剖分，求神犇调出 TLE 的 50 分

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::lower_bound;
using std::max;
using std::min;
using std::pair;
using std::priority_queue;
using std::sort;
using std::string;
using std::upper_bound;
using std::vector;
// using LL = long long;
const int MAXN = 100005;
int n, m;
int cnt = 0;
int fa[MAXN], top[MAXN], dep[MAXN], son[MAXN], siz[MAXN], dfn[MAXN], rk[MAXN],
    ys[MAXN];
struct edge {
  int v, w, id;
};
vector<edge> g[MAXN];
void dfs1(int u) {
  son[u] = -1;
  siz[u] = 1;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].v;
    if (dep[v])
      continue;
    ys[g[u][i].id] = v;
    dep[v] = dep[u] + 1;
    fa[v] = u;
    dfs1(v);
    siz[u] += siz[v];
    if (son[u] == -1 || siz[son[u]] < siz[v])
      son[u] = v;
  }
}
void dfs2(int u, int t, int val = -1) {
  top[u] = t;
  cnt++;
  dfn[u] = cnt;
  if (~val) {
    rk[cnt] = val;
  }
  if (son[u] == -1)
    return;
  int tw = 0;
  for (int i = 0; i < g[u].size(); i++) {
    if (g[u][i].v == son[u]) {
      tw = g[u][i].w;
      break;
    }
  }
  dfs2(son[u], t, tw);
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].v;
    if (v != son[u] && fa[u] != v)
      dfs2(v, v, g[u][i].w);
  }
}
struct node {
  int l, r, lazy, maxx;
} tree[4 * MAXN];
void build(int u, int l, int r) {
  tree[u].l = l;
  tree[u].r = r;
  if (l == r) {
    tree[u].maxx = rk[l];
    return;
  }
  int m = (l + r) >> 1;
  build(u << 1, l, m);
  build(u << 1 | 1, m + 1, r);
  tree[u].maxx = max(tree[u << 1].maxx, tree[u << 1 | 1].maxx);
}
void pushdown(int u) {
  if (tree[u].lazy != 0) {
    tree[u << 1].lazy = tree[u].lazy;
    tree[u << 1 | 1].lazy = tree[u].lazy;
    tree[u << 1].maxx = tree[u].lazy;
    tree[u << 1 | 1].maxx = tree[u].lazy;
  }
  tree[u].lazy = 0;
}
void change(int u, int x, int t) {
  if (tree[u].r < x || tree[u].l > x)
    return;
  if (tree[u].l >= x && tree[u].r <= x) {
    tree[u].maxx = t;
    tree[u].lazy = t;
    return;
  }
  pushdown(u);
  change(u << 1, x, t);
  change(u << 1 | 1, x, t);
  tree[u].maxx = max(tree[u << 1].maxx, tree[u << 1 | 1].maxx);
}
int query(int u, int x, int y) {
  if (tree[u].r < x || tree[u].l > y)
    return 0;
  if (tree[u].l == tree[u].r)
    return tree[u].maxx;
  pushdown(u);
  return max(query(u << 1, x, y), query(u << 1 | 1, x, y));
}
int main() {
  std::ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].push_back({v, w, i + 1});
    g[v].push_back({u, w, i + 1});
  }
  dep[1] = 1;
  dfs1(1);
  dfs2(1, 1);
  build(1, 1, cnt);
  string op;
  cin >> op;
  while (op != "DONE") {
    int u, v;
    cin >> u >> v;
    if (op == "CHANGE") {
      change(1, dfn[ys[u]], v);
    } else {
      if (u == v) {
        cout << 0 << endl;
      } else {
        int res = -1e9;
        while (top[u] != top[v]) {
          if (dep[top[u]] < dep[top[v]])
            std::swap(u, v);
          res = max(res, query(1, dfn[top[u]], dfn[u]));
          u = fa[top[u]];
        }
        if (dep[u] > dep[v])
          std::swap(u, v);
        cout << max(res, query(1, dfn[u] + 1, dfn[v])) << endl;
      }
    }
    cin >> op;
  }
  return 0;
}