View difference between Paste ID: G8ea5kST and Y4U0g8Sz

 #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;
 }