func_code_string: #include <bits/stdc++.h>   using namespace std;   const int inft = 1000000009;   const int mod = 1000000007;   const int MAXN = 100006;   int f[MAXN];   const int N = MAXN, P = MAXN;   vector<int> G[N];   pair<int, int> E[MAXN], Q[MAXN];   int C[MAXN];   namespace LCAO {   vector<pair<int, int> > pyt[N];   int LCA[P];   int kolor[N], REP[N], przodek[N];   int find(int first) {     return REP[first] < 0 ? first : REP[first] = find(REP[first]);   }   void DfsTarjan(int first, int par) {     kolor[first] = 1;     REP[first] = -1;     przodek[first] = first;     for (typeof((G[first]).begin()) it = (G[first]).begin();          it != (G[first]).end(); ++it)       if (*it != par) {         DfsTarjan(*it, first);         int a = find(first), b = find(*it);         if (REP[a] < REP[b]) swap(a, b);         REP[b] += REP[a];         REP[a] = b;         przodek[b] = first;       }     for (typeof((pyt[first]).begin()) it = (pyt[first]).begin();          it != (pyt[first]).end(); ++it)       if (kolor[it->first] == 2) {         int lca = przodek[find(it->first)];         LCA[it->second] = lca;       }     kolor[first] = 2;   }   void dodaj_krawedz(int a, int b) {     G[a].push_back(b);     G[b].push_back(a);   }   int nr = 0;   void dodaj_pytanie(int a, int b) {     if (a == b)       LCA[nr] = a;     else {       pyt[a].push_back(pair<int, int>(b, nr));       pyt[b].push_back(pair<int, int>(a, nr));     }     nr++;   }   void czysc(int n = N) {     for (int i = 0; i < (n); ++i) G[i].clear(), pyt[i].clear(), kolor[i] = 0;     nr = 0;   }   }  // namespace LCAO   pair<int, pair<int, int> > rev(pair<int, pair<int, int> > a) {     return pair<int, pair<int, int> >(         a.first, pair<int, int>(a.second.second, a.second.first));   }   pair<int, pair<int, int> > merge(pair<int, pair<int, int> > t1,                                    pair<int, pair<int, int> > t2) {     ;     if (t1.first == -inft) {       if (t2.first == -inft) {         ;         return pair<int, pair<int, int> >(             -inft, pair<int, int>(t1.second.first + t2.second.first,                                   t1.second.first + t2.second.first));       } else {         ;         return pair<int, pair<int, int> >(             t2.first,             pair<int, int>(t1.second.first + t2.second.first, t2.second.second));       }     } else if (t2.first == -inft) {       ;       return pair<int, pair<int, int> >(           t1.first,           pair<int, int>(t1.second.first, t1.second.second + t2.second.second));     };     return pair<int, pair<int, int> >(         t1.first + t2.first + f[t1.second.second + t2.second.first],         pair<int, int>(t1.second.first, t2.second.second));   }   int eval(pair<int, pair<int, int> > t1) {     ;     if (t1.first == -inft) return f[t1.second.first];     return f[t1.second.first] + f[t1.second.second] + t1.first;   }   struct drzewo {     int T;     vector<pair<int, pair<int, int> > > drz;     void init(int n) {       T = 1;       while (T < n) T *= 2;       drz.resize(2 * T, pair<int, pair<int, int> >(0, pair<int, int>(0, 0)));     }     void update(int a, int b) {       assert(a == b);       a += T;       drz[a] = pair<int, pair<int, int> >(-inft, pair<int, int>(1, 1));       a /= 2;       while (a) {         drz[a] = merge(drz[2 * a], drz[2 * a + 1]);         a /= 2;       }     }     pair<int, pair<int, int> > get(int a, int b) {       pair<int, pair<int, int> > ret1 =           pair<int, pair<int, int> >(-inft, pair<int, int>(0, 0));       pair<int, pair<int, int> > ret2 =           pair<int, pair<int, int> >(-inft, pair<int, int>(0, 0));       a += T;       b += T;       while (a <= b) {         if (a % 2 == 1) {           ret1 = merge(ret1, drz[a]);           a++;         }         if (b % 2 == 0) {           ret2 = merge(drz[b], ret2);           b--;         }         a /= 2;         b /= 2;       }       return merge(ret1, ret2);     }   };   namespace HLD {   drzewo CS[N];   int nrc[N];   int ind[N];   int hop[N];   int siz[N];   int sciezek;   pair<int, pair<int, int> > get(int a, int anc) {     ;     pair<int, pair<int, int> > ret(-inft, pair<int, int>(0, 0));     while (nrc[a] != nrc[anc]) {       ret = merge(ret, rev(CS[nrc[a]].get(0, ind[a])));       a = hop[nrc[a]];     }     ret = merge(ret, rev(CS[nrc[a]].get(ind[anc] + 1, ind[a])));     ;     return ret;   }   void update(int a, int anc) {     ;     while (nrc[a] != nrc[anc]) {       CS[nrc[a]].update(0, ind[a]);       a = hop[nrc[a]];     }     CS[nrc[a]].update(ind[anc], ind[a]);   }   int rozm(int u, int pr) {     siz[u] = 1;     for (typeof((G[u]).begin()) it = (G[u]).begin(); it != (G[u]).end(); ++it)       if (*it != pr) siz[u] += rozm(*it, u);     return siz[u];   }   void ciezka(int u, int pr, int csc, int index) {     nrc[u] = csc;     ind[u] = index;     int dz = -1;     for (typeof((G[u]).begin()) it = (G[u]).begin(); it != (G[u]).end(); ++it)       if (*it != pr && (dz == -1 || siz[*it] > siz[dz])) dz = *it;     for (typeof((G[u]).begin()) it = (G[u]).begin(); it != (G[u]).end(); ++it)       if (*it == dz)         ciezka(*it, u, csc, index + 1);       else if (*it != pr) {         hop[sciezek++] = u;         ciezka(*it, u, sciezek - 1, 0);       }     if (dz == -1) {       CS[csc].init(index + 1);     }   }   void init(int root) {     rozm(root, -1);     sciezek = 1;     hop[0] = -1;     ciezka(root, -1, 0, 0);   }   }  // namespace HLD   void solve() {     int n, q;     scanf( %d%d , &n, &q);     f[0] = 0;     for (int i = 0; i < (n - 1); ++i) {       scanf( %d , &f[i + 1]);     }     vector<pair<int, int> > EV;     for (int i = 0; i < (n - 1); ++i) {       int a, b, c;       scanf( %d%d%d , &a, &b, &c);       a--;       b--;       LCAO::dodaj_krawedz(a, b);       E[i] = pair<int, int>(a, b);       EV.push_back(pair<int, int>(c + 1, -(i + 1)));     }     for (int i = 0; i < (q); ++i) {       int a, b, c;       scanf( %d%d%d , &a, &b, &c);       a--;       b--;       LCAO::dodaj_pytanie(a, b);       Q[i] = pair<int, int>(a, b);       EV.push_back(pair<int, int>(c, i));     }     vector<int> ANS(q);     LCAO::DfsTarjan(0, -1);     HLD::init(0);     for (int i = 0; i < (n - 1); ++i)       if (HLD::siz[E[i].first] > HLD::siz[E[i].second])         swap(E[i].first, E[i].second);     sort((EV).begin(), (EV).end());     reverse((EV).begin(), (EV).end());     for (typeof((EV).begin()) it = (EV).begin(); it != (EV).end(); ++it) {       if (it->second >= 0) {         ;         int u = LCAO::LCA[it->second], u1 = Q[it->second].first,             u2 = Q[it->second].second;         pair<int, pair<int, int> > t1 = HLD::get(u1, u), t2 = HLD::get(u2, u);         t1 = merge(t1, rev(t2));         ANS[it->second] = eval(t1);       } else {         int u = -it->second - 1;         ;         HLD::update(E[u].first, E[u].first);       }     }     for (typeof((ANS).begin()) it = (ANS).begin(); it != (ANS).end(); ++it)       printf( %d n , *it);   }   int main() {     int te = 1;     for (int ti = 0; ti < (te); ++ti) solve();     return 0;   }   