Mxqz

代码：

#include<bits/stdc++.h>

#define endl '\n';
#define int long long

using namespace std;

const int N = 3e5 + 1;

int n, m;
int a[N], new_w[N];

int dep[N], size[N], son[N], fa[N], top[N], id[N];
int sum;

int tree[N * 4], tag[N * 4];

void pushup(int node){
    tree[node] = max(tree[node << 1], tree[node << 1 | 1]);
}

void build(int node, int lt, int rt){
    if(lt == rt){
        tree[node] = new_w[id[lt]];
        return ;
    }
    int mid = lt + rt >> 1;
    build(node << 1, lt, mid);
    build(node << 1 | 1, mid + 1, rt);
    pushup(node);
}

void update(int cur, int lt, int rt, int x, int y, int val){
  if(x > rt || y < rt){
    return ;
  }
  if(lt == rt && x <= lt && rt <= y){
    tree[cur] = val;
    return ;
  }
  int mid = lt + rt >> 1;
  update(cur << 1, lt, mid, x, y, val);
  update((cur << 1) + 1, mid + 1, rt, x, y, val);
  pushup(cur);
}

int query(int cur, int lt, int rt, int x, int y){
  if(x > rt || y < lt){
    return -1e9;
  }
  if(x <= lt && rt <= y){
    return tree[cur];
  }
  int mid = lt + rt >> 1;
  return max(query(cur << 1, lt, mid, x, y), query((cur << 1) + 1, mid + 1, rt, x, y));
}

int head[N], tot;
int v[N];

struct Node{
  int to, w, next;
}edges[N * 2];

void add(int u, int v, int w){
  tot++;
  edges[tot].to = v;
  edges[tot].w = w;
  edges[tot].next = head[u];
  head[u] = tot;
}

void dfs1(int x, int f){
  fa[x] = f;
  size[x] = 1;
  dep[x] = dep[f] + 1;
  int maxi = -1e9;
  for(int i = head[x]; i; i = edges[i].next){
    if(edges[i].to != f){
        new_w[edges[i].to] = edges[i].w;
        v[i] = edges[i].to;
      dfs1(edges[i].to, x);
      size[x] += size[edges[i].to];
      if(size[edges[i].to] > maxi){
        maxi = size[edges[i].to];
        son[x] = edges[i].to;
      }
    }
  }
}

void dfs2(int x, int t){
  top[x] = t;
  id[x] = ++sum;
  if(!son[x]){
    return ;
  }
  dfs2(son[x], t);
  for(int i = head[x]; i; i = edges[i].next){
    if(edges[i].to != son[x] && edges[i].to != fa[x]){
      dfs2(edges[i].to, edges[i].to);
    }
  }
}

int Query1(int x, int y){
  int ans = 0;
  while(top[x] != top[y]){
    if(dep[top[x]] < dep[top[y]]){
      swap(x, y);
    }
    ans = max(ans, query(1, 1, n, id[top[x]], id[x]));
    x = fa[top[x]];
  }
  if(dep[x] > dep[y]){
    swap(x, y);
  }
  ans = max(ans, query(1, 1, n, id[x], id[y]));
  return ans;
}

signed main(){
  cin >> n;
  for(int i = 1; i < n; i++){
    int u, v, w;
    cin >> u >> v >> w;
    add(u, v, w);
    add(v, u, w);
  }
  dfs1(1, 0);
  dfs2(1, 1);
    build(1, 1, n);
  while(true){
    string op;
    cin >> op;
    if(op == "DONE"){
      return 0;
    }
    else if(op == "CHANGE"){
      int x, k;
      cin >> x >> k;
      update(1, 1, n, id[v[x]], id[v[x]], k);
    }
    else{
      int x, y;
      cin >> x >> y;
      if(x == y){
        cout << 0 << '\n';
            }
            else{
                cout << Query1(x, y) << '\n';
            }
    }
  }
  return 0;
}