【TLE】40pts 求调

疑似 vector 被卡常？

#include <stdio.h>
#include <string.h>
#include <vector>
#define mx(x, y) ((x) > (y) ? (x) : (y))
#define swp(x, y) ((x) ^= (y) ^= (x) ^= (y))
#define int long long
//#pragma GCC optimize(2)
template<typename Tp>
inline void Read(Tp &x) {
    x = 0; int w = 0; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') w ^= 1;
    for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    if (w) x = -x;
}
const int N = (int)1e5 + 5;
int n, sz[N], dep[N], tp[N], son[N], fa[N], ti[N], dc;
struct Edge {int u, v, w;} ed[N];
std:: vector<int> e[N];
inline void init() {
    dc = 0;
//  memset(sz, 0, sizeof sz);
//  memset(dep, 0, sizeof dep);
//  memset(tp, 0, sizeof tp);
    memset(son, 0, sizeof son);
//  memset(fa, 0, sizeof fa);
//  memset(ti, 0, sizeof ti);
    for (int i = 1; i <= n; ++i) e[i].clear();
}
inline void dfs_find(int u, int pa, int dept) {
    sz[u] = 1, dep[u] = dept, son[u] = 0, fa[u] = pa;
    for (int i = 0; i < e[u].size(); ++i) {
        int v = e[u][i];
        if (v == pa) continue;
        dfs_find(v, u, dept + 1);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
inline void dfs_time(int u, int top) {
    ti[u] = ++dc; tp[u] = top;
    if (son[u]) dfs_time(son[u], top);
    for (int i = 0; i < e[u].size(); ++i) {
        int v = e[u][i];
        if (v == son[u] || v == fa[u]) continue;
        dfs_time(v, v);
    }
}
struct Node {int val, maxw;} tr[N << 2];
inline void pushup(int id) {
    tr[id].maxw = mx(tr[id << 1].maxw, tr[id << 1 | 1].maxw);
}
inline void build(int id, int l, int r) {
    tr[id].val = tr[id].maxw = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}
inline void update(int id, int l, int r, int pos, int keyw) {
    if (l == r) {tr[id].val = tr[id].maxw = keyw; return;}
    int mid = l + r >> 1;
    if (pos <= mid) update(id << 1, l, mid, pos, keyw);
    else update(id << 1 | 1, mid + 1, r, pos, keyw);
    pushup(id);
}
inline int query(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) return tr[id].maxw;
    int mid = l + r >> 1, Res = 0;
    if (x <= mid) Res = mx(query(id << 1, l, mid, x, y), Res);
    if (y > mid) Res = mx(query(id << 1 | 1, mid + 1, r, x, y), Res);
    return Res;
}
inline int lca(int x, int y) {
    int Res = 0;
    while (tp[x] != tp[y]) {
        if (dep[tp[x]] < dep[tp[y]]) swp(x, y);
        Res = mx(query(1, 1, n, ti[tp[x]], ti[x]), Res);
        x = fa[tp[x]];
    }
    if (dep[x] > dep[y]) swp(x, y);
    if (x != y) Res = mx(query(1, 1, n, ti[x] + 1, ti[y]), Res);
    return Res;
}
signed main(void) {
//  freopen("qtree.in", "r", stdin); freopen("qtree.out", "w", stdout);
    Read(n); init();
    for (int i = 1; i < n; ++i) {
        Read(ed[i].u), Read(ed[i].v), Read(ed[i].w);
        e[ed[i].u].push_back(ed[i].v), e[ed[i].v].push_back(ed[i].u);
    }
    dfs_find(1, 1, 1); dfs_time(1, 1); build(1, 1, n);
    for (int i = 1; i < n; ++i) {
        if (dep[ed[i].u] > dep[ed[i].v]) swp(ed[i].u, ed[i].v);
        update(1, 1, n, ti[ed[i].v], ed[i].w);
    }
    char qu[10];
    for (int a, b; ; ) {
        scanf("%s", qu);
        if (qu[0] == 'D') break;
        Read(a), Read(b);
        if (qu[0] == 'C') update(1, 1, n, ti[ed[a].v], b);
        if (qu[0] == 'Q') printf("%lld\n", lca(a, b));
    }
    return 0;
}