RT，这份代码中的线段树部分（即 Seg 结构体）有问题，换成正常的线段树可 AC。

打算用这题来练习非递归线段树的，现在找不到 bug 在哪，求调。

其中 Cha 为单点修改，Fil 为区间推平，Add 为区间加。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;

#define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define each(i, x) for (auto &&i : (x))
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define dbg(x) (cerr << "(dbg) " << #x " = " << (x) << '\n')
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define up(x, y) (((x) < (y)) && ((x) = (y)))
#define down(x, y) (((x) > (y)) && ((x) = (y)))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))

const int N = 2e5 + 9;

struct G {
  int h[N], tot;
  struct E {
    int t, n, v;
  } e[N];
  void Add(int f, int t, int v) { e[++tot] = {t, h[f], v}, h[f] = tot; }
} g;

int n, tim, dfn[N], son[N], sz[N], fa[N], dep[N], a[N], tp[N];

struct Seg {
  struct T {
    int add, fil, mx;
    void Fil(int x) { fil = x, add = 0, mx = x; }
    void Add(int x) { add += x, mx += x; }
  } d[N << 2];
  int M, T;

  void Down(int u) {
    per (i, T, 1) {
      int v = u >> i;
      if (d[v].fil) d[v << 1].Fil(d[v].fil), d[v << 1 | 1].Fil(d[v].fil), d[v].fil = 0;
      if (d[v].add) d[v << 1].Add(d[v].add), d[v << 1 | 1].Add(d[v].add), d[v].add = 0;
    }
  }

  void Up(int u) {
    while (u > 1) u >>= 1, d[u].mx = max(d[u << 1].mx, d[u << 1 | 1].mx);
  }

  void Build() {
    for (T = 1, M = 1; M <= n; M <<= 1) ++T;
    rep (i, M + 1, M + n)
      d[i].mx = a[i - M];
    per (i, M - 1, 1)
      d[i].mx = max(d[i << 1].mx, d[i << 1 | 1].mx);
  }

  void Cha(int u, int x) { u += M, Down(u), d[u].mx = x, Up(u); }

  void Add(int l, int r, int x) {
    l += M, r += M;
    int l0 = l, r0 = r;
    for (--l, ++r; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (~l & 1) d[l ^ 1].Add(x);
      if (r & 1) d[r ^ 1].Add(x);
    }
    Down(l0), Down(r0);
    Up(l0), Up(r0);
  }

  void Fil(int l, int r, int x) {
    l += M, r += M;
    int l0 = l, r0 = r;
    for (--l, ++r; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (~l & 1) d[l ^ 1].Fil(x);
      if (r & 1) d[r ^ 1].Fil(x);
    }
    Down(l0), Down(r0);
    Up(l0), Up(r0);
  }

  int Ask(int l, int r) {
    l += M, r += M;
    Down(l), Down(r);
    ll ans = 0;
    for (--l, ++r; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (~l & 1) up(ans, d[l ^ 1].mx);
      if (r & 1) up(ans, d[r ^ 1].mx);
    }
    return ans;
  }
} seg;

void Dfs1(int f) {
  dep[f] = dep[fa[f]] + 1;
  // dbg(f);
  sz[f] = 1;
  nxt (i, f, g) {
    int t = g.e[i].t;
    if (t == fa[f]) continue;
    fa[t] = f, Dfs1(t), sz[f] += sz[t];
    if (sz[t] > sz[son[f]]) son[f] = t;
  }
}

void Dfs2(int f) {
  dfn[f] = ++tim;
  // dbg(f);
  if (!son[f]) return;
  nxt (i, f, g) {
    int t = g.e[i].t;
    if (t == fa[f]) continue;
    if (t != son[f]) continue;
    tp[t] = tp[f], Dfs2(t), a[dfn[t]] = g.e[i].v;
  }
  nxt (i, f, g) {
    int t = g.e[i].t;
    if (t == fa[f]) continue;
    if (t == son[f]) continue;
    tp[t] = t, Dfs2(t), a[dfn[t]] = g.e[i].v;
  }
}

char op[10];

void Cha(int x, int y) { seg.Cha(max(dfn[g.e[x * 2 - 1].t], dfn[g.e[x * 2].t]), y); }

void Add(int f, int t, int x) {
  while (tp[f] != tp[t]) {
    if (dep[tp[f]] > dep[tp[t]]) swap(f, t);
    seg.Add(dfn[tp[t]], dfn[t], x);
    t = fa[tp[t]];
  }
  if (dfn[f] > dfn[t]) swap(f, t);
  if (f != t) seg.Add(dfn[f] + 1, dfn[t], x);
}

void Fil(int f, int t, int x) {
  while (tp[f] != tp[t]) {
    if (dep[tp[f]] > dep[tp[t]]) swap(f, t);
    seg.Fil(dfn[tp[t]], dfn[t], x);
    t = fa[tp[t]];
  }
  if (dfn[f] > dfn[t]) swap(f, t);
  if (f != t) seg.Fil(dfn[f] + 1, dfn[t], x);
}

int Ask(int f, int t) {
  int ans = 0;
  while (tp[f] != tp[t]) {
    if (dep[tp[f]] > dep[tp[t]]) swap(f, t);
    // cerr << dfn[tp[t]] << ' ' << dfn[t] << ' ' << seg.Ask(dfn[tp[t]], dfn[t]) << '\n';
    up(ans, seg.Ask(dfn[tp[t]], dfn[t]));
    // dbg(ans);
    t = fa[tp[t]];
  }
  if (dfn[f] > dfn[t]) swap(f, t);
  // dbg(f);
  // dbg(t);
  // cerr << dfn[f] + 1 << ' ' << dfn[t] << ' ' << seg.Ask(dfn[f] + 1, dfn[t]) << '\n';
  if (f != t) up(ans, seg.Ask(dfn[f] + 1, dfn[t]));
  // cerr << "----------" << '\n';
  return ans;
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  re (i, n - 1) {
    int f, t, v;
    cin >> f >> t >> v;
    g.Add(f, t, v), g.Add(t, f, v);
  }
  Dfs1(1);
  tp[1] = 1, Dfs2(1);
  // re (i, n)
  //   cerr << a[i] << ' ';
  // cerr << '\n';
  seg.Build();
  while (1) {
    cin >> op;
    if (*op == 'S')
      break;
    else if (op[1] == 'h') {
      int x, y;
      cin >> x >> y;
      Cha(x, y);
    } else if (op[1] == 'o') {
      int x, y, z;
      cin >> x >> y >> z;
      Fil(x, y, z);
    } else if (op[1] == 'd') {
      int x, y, z;
      cin >> x >> y >> z;
      Add(x, y, z);
    } else {
      int x, y;
      cin >> x >> y;
      int res = Ask(x, y);
      cout << res << '\n';
    }
    // re (i, seg.M + n)
    //   cerr << i << ' ' << seg.d[i].fil << ' ' << seg.d[i].add << ' ' << seg.d[i].mx << '\n';
    // cerr << "==========\n";
  }
  return 0;
}