View difference between Paste ID: FZnjHPsT and 1amnAc8r

 # include <iostream>
 # include <fstream>
 # include <sstream>
 # include <algorithm>
 # include <numeric>
 # include <cstdio>
 # include <cmath>
 # include <cstdlib>
 # include <cstring>
 # include <vector>
 # include <list>
 # include <set>
 # include <map>
 # include <iomanip>
 # include <stack>
 # include <queue>
 # include <cctype>
 # include <climits>
 # include <assert.h>
 
 using namespace std;
 
 //conversion
 //------------------------------------------
 inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
 template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 typedef long long LL;
 typedef unsigned long long ULL;
 typedef vector<int> VI;
 typedef vector<VI> VVI;
 typedef vector<LL> VLL;
 typedef pair<int,int> PII;
 typedef pair<int, PII> TIII;
 typedef vector<PII> VPII;
 typedef vector<double> VD;
 typedef pair<double,double> PDD;
 
 const int inf=1000000000;
 const LL INF=LL(inf)*inf;
 const double eps=1e-9;
 const double PI=2*acos(0.0);
 
 #define GI ({int t;scanf("%d",&t);t;})
 #define REP(i,a,b) for(int i=a;i<b;i++)
 #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
 #define ALL(v) (v).begin(),(v).end()
 #define RALL(a) (a).rbegin(), (a).rend()
 #define TR(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
 #define bit(n) (1<<(n))
 #define bit64(n) ((LL(1))<<(n))
 #define PB push_back
 #define SZ size()
 #define MP make_pair
 #define CL clear()
 #define fill(ar,val) memset((ar),(val), sizeof(ar))
 #define MIN(a,b) {if((a)>(b)) (b);}
 #define MAX(a,b) {if((a)<(b)) (b);}
 #define EXIST(s,e) ((s).find(e)!=(s).end())
 #define SORT(c) sort((c).begin(),(c).end())
 #define MT(a,b,c) MP(a, MP(b, c))
 #define sqr(x) ((x)*(x))
 #define X first
 #define Y second
 #define REP(i,a,b) for(int i=a;i<b;i++)
 #define GI ({int t;scanf("%d",&t);t;})
 #define DBPRINT cout << "HERE" << debugptr++
 int debugptr = 0;
 
 //clock_t start=clock();
 //fprintf(stderr,"time=%.3lfsec\n",0.001*(clock()-start));
 
 #define MAXN 10003
 #define MAXLN 14
 #define root 1
 
 int ptr;
-int par[MAXN][MAXLN];
+int par[MAXN];
 int chainNo;
 
 VI adj_list[MAXN];
 VI costs[MAXN];
 VI indexx[MAXN];
 int L[MAXN];
 int baseArray[MAXN];
 int posInBase[MAXN];
 int other_end[MAXN];
 int subsize[MAXN];
 int chain[MAXN];
 int head_of_chain[MAXLN];
 int pos_in_chain[MAXN];
 int st[1 << (MAXLN + 1) + 5];
 
 void construct(int i, int st_s, int st_e) {
     if (st_s == st_e) {
         st[i] = baseArray[st_s];
         return;
     }
     int mid = (st_s+st_e)/2;
     construct(2*i+1, st_s, mid);
     construct(2*i+2, mid+1, st_e);
     st[i] = max(st[2*i+1],st[2*i+2]);
 }
 
 void update(int i, int st_s, int st_e, int s, int val) {
     if (st_s > s || st_e < s) return;
     if (st_s == st_e && st_s == s) {
         st[i] = val;
         return;
     }
     int mid = (st_s+st_e)/2;
     update(2*i+1, st_s, mid,s,val);
     update(2*i+2, mid+1, st_e,s,val);
     st[i] = max(st[2*i+1],st[2*i+2]);
 }
 
 int query(int i, int st_s, int st_e, int s, int e) {
     if (st_s > e || st_e < s) return 0;
     if (s <= st_s && st_e <= e)  {
         return st[i];
     }
     int mid = (st_s+st_e)/2;
     return max(query(2*i+1, st_s, mid,s, e),query(2*i+2, mid+1, st_e,s,e));
 }
 
 void HLD(int curr, int prev, int cost) {
     if (head_of_chain[chainNo] == -1) {
         head_of_chain[chainNo] = curr;
     }
 
     chain[curr] = chainNo;
     posInBase[curr] = ptr;
     baseArray[ptr++] = cost;
 
     int sc = -1;
     int mss = 0;
     int nc = 0;
     REP(i,0,adj_list[curr].size()) {
         if (adj_list[curr][i] != prev && subsize[adj_list[curr][i]] > mss) {
             sc = adj_list[curr][i];
             nc = costs[curr][i];
             mss = subsize[adj_list[curr][i]];
         }
     }
 
     if (sc != -1) {
         HLD(sc,curr,nc);
     }
 
     REP(i,0,adj_list[curr].size()) {
         if (adj_list[curr][i] != prev && adj_list[curr][i] != sc) {
             chainNo++;
             HLD(adj_list[curr][i], curr, costs[curr][i]);
         }
     }
 }
 
 void dfs(int r, int p, int d = 0) {
-    par[r][0] = p;
+    par[r] = p;
     subsize[r] = 1;
     L[r] = d;
     REP(i,0,adj_list[r].size()) {
         if (adj_list[r][i] != p) {
             other_end[indexx[r][i]] = adj_list[r][i];
             dfs(adj_list[r][i],r,d+1);
             subsize[r] += subsize[adj_list[r][i]];
         }
     }
 }
 
 void change(int a, int b) {
     int u = other_end[a];
     update(0,0,ptr,posInBase[u],b);
 }
 
-int LCS(int u, int v) {
+int LCA(int u, int v) {
     while (chain[u] != chain[v]) {
-        if (L[u] > L[v]) {
+        if (L[head_of_chain[chain[u]]] > L[head_of_chain[chain[v]]]) {
             u = head_of_chain[chain[u]];
-            u = par[u][0];
+            assert(u==1 || par[u] != -1);
             u = par[u];
         }
         else {
-            v = par[v][0];
+
             assert(par[v] != -1);
             v = par[v];
         }
     }
     if (L[u] < L[v]) return u;
     return v;
 }
 
 int q(int a, int b) {
     if (a == b) return 0;
     int achain, bchain = chain[b], ans = -1;
     while(1) {
         achain = chain[a];
-            ans = max(ans,query(0,0,ptr,posInBase[a],posInBase[b]));
+
             if (a == b) break;
             ans = max(ans,query(0,0,ptr,posInBase[b],posInBase[a]));
             break;
         }
-        a = par[a][0];
+
         a = head_of_chain[achain];
         a = par[a];
     }
     return ans;
-int query(int a, int b) {
+
-    int lcs = LCS(a, b);
+
-    return max(q(lcs,a), q(lcs,b));
+int mquery(int a, int b) {
     int lca = LCA(a, b);
     return max(q(a,lca), q(b,lca));
 }
 
 int main(void) {
     ios_base::sync_with_stdio(0);
 #ifndef ONLINE_JUDGE
     freopen("i.txt","r",stdin);
 //    freopen("o.txt","w",stdout);
 #endif
     int T;
     cin >> T;
     REP(i,0,T) {
         ptr = chainNo = 0;
         memset(head_of_chain, -1, sizeof head_of_chain);
         int N; cin >> N;
         REP(j,0,N+1) {
             adj_list[j].clear();
-            REP(k,0,MAXLN) par[j][k] = -1;
+
             indexx[j].clear();
             par[j] = -1;
         }
         REP(j,1,N) {
             int a, b, c;
             cin >> a >> b >> c;
             adj_list[a].PB(b);
             adj_list[b].PB(a);
             costs[a].PB(c);
             costs[b].PB(c);
             indexx[a].PB(j);
             indexx[b].PB(j);
         }
         dfs(root,-1);
         HLD(root, -1, 0);
         construct(0,0,ptr);
         string s; int p1,p2;
         cin >> s;
         while(s[0] != 'D') {
             cin >> p1 >> p2;
             if (s[0] == 'C') {
                 change(p1,p2);
-                cout << query(p1,p2) << endl;
+
             else {
                 cout << mquery(p1,p2) << endl;
             }
             cin >> s;
         }
         /*
         REP(l,0,2*N) {
             cout << st[l] << " ";
         }
         cout << "L " << LCA(4,5);
         cout << endl;
         */
     }
     return 0;
 }