func_code_string: #include <bits/stdc++.h>   using namespace std;   int n;   vector<int> v;   vector<tuple<int, int, int> > g[300002];   vector<pair<int, long long int> > vv[300002];   vector<pair<long long int, long long int> > V[300002];   long long int dist[300002];   priority_queue<pair<long long int, int>, vector<pair<long long int, int> >,                  greater<pair<long long int, int> > >       q;   struct st {     long long int dp[2][2];     int l;     int r;     st() {       dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = LLONG_MAX;       l = -1;       r = -1;     }     void set_node(int x) {       dp[0][0] = 0;       dp[1][1] = 0;       dp[0][1] = dist[x];       dp[1][0] = dist[x];       l = r = x;     }     st flip() {       swap(l, r);       swap(dp[0][1], dp[1][0]);       return (*this);     }   };   map<pair<int, int>, long long int> mp;   pair<long long int, long long int> look[300002];   int dep[300002];   int lcc[19][300002];   st pat[19][300002];   inline long long int ds(int t1, int node1, int t2, int node2) {     if (lcc[0][node1] != node2) swap(node1, node2);     if (t1 == 0) {       return look[node1].first;     } else {       return look[node1].second;     }   }   inline st merge(st a, st b) {     if (a.l == -1) {       return b;     }     if (b.l == -1) {       return a;     }     st r;     r.l = a.l;     r.r = b.r;     long long int w[] = {ds(0, a.r, 0, b.l), ds(1, a.r, 1, b.l)};     for (int i = 0; i < 2; i++) {       for (int j = 0; j < 2; j++) {         for (int k = 0; k < 2; k++) {           long long int cs = a.dp[i][j] + b.dp[j][k];           cs += w[j];           r.dp[i][k] = min(r.dp[i][k], cs);         }       }     }     return r;   }   inline void dfs(int a, int d = 0, int p = -1,                   pair<long long int, long long int> c = make_pair(-1, -1)) {     lcc[0][a] = p;     dep[a] = d;     look[a] = c;     int idx = 0;     for (auto go : vv[a]) {       if (go.first == p) {         idx++;         continue;       }       dfs(go.first, d + 1, a, V[a][idx]);       idx++;     }   }   int lca(int a, int b) {     if (dep[a] < dep[b]) swap(a, b);     for (int i = 0; i < 19; i++) {       if (((dep[a] - dep[b]) >> i) & 1) {         a = lcc[i][a];       }     }     if (a == b) return a;     for (int i = 19 - 1; i >= 0; i--) {       if (lcc[i][a] != lcc[i][b]) {         a = lcc[i][a];         b = lcc[i][b];       }     }     return lcc[0][a];   }   inline st go(int a, int f) {     st r;     if (f == 0) {       return r;     }     for (int i = 0; i < 19; i++) {       if ((f >> i) & 1) {         r = merge(r, pat[i][a]);         a = lcc[i][a];       }     }     return r;   }   int qq;   int main() {     cin >> n;     for (int i = 0; i < n; i++) {       long long int w;       scanf( %lld , &w);       v.push_back(w);       vv[n].push_back(make_pair(i, w));     }     for (int i = 1; i < n; i++) {       long long int a, b, c, d;       scanf( %lld%lld%lld%lld , &a, &b, &c, &d);       a--;       b--;       if (a < b) mp[make_pair(a, b)] = c;       if (b < a) mp[make_pair(b, a)] = c;       if (a < b) mp[make_pair(a + n, b + n)] = d;       if (b < a) mp[make_pair(b + n, a + n)] = d;       g[a].push_back(make_tuple(b, c, d));       g[b].push_back(make_tuple(a, c, d));       vv[a].push_back(make_pair(b, c + d));       vv[b].push_back(make_pair(a, c + d));       V[a].push_back(make_pair(c, d));       V[b].push_back(make_pair(c, d));     }     memset(dist, -1, sizeof(dist));     dist[n] = 0;     q.push(make_pair(0, n));     while (!q.empty()) {       int b = q.top().second;       long long int cc = q.top().first;       q.pop();       if (dist[b] != cc) continue;       for (auto go : vv[b]) {         if (dist[go.first] == -1 || dist[go.first] > dist[b] + go.second) {           dist[go.first] = dist[b] + go.second;           q.push(make_pair(dist[go.first], go.first));         }       }     }     dfs(0);     for (int j = 0; j < n; j++) {       pat[0][j].set_node(j);     }     for (int i = 0; i + 1 < 19; i++) {       for (int j = 0; j < n; j++) {         if (lcc[i][j] != -1) {           lcc[i + 1][j] = lcc[i][lcc[i][j]];           pat[i + 1][j] = merge(pat[i][j], pat[i][lcc[i][j]]);         } else {           lcc[i + 1][j] = -1;         }       }     }     cin >> qq;     while (qq--) {       int l, r;       scanf( %d%d , &l, &r);       l--;       r--;       l = (l / 2) + (l % 2) * n;       r = (r / 2) + (r % 2) * n;       int L = l;       int R = r;       if (L >= n) L -= n;       if (R >= n) R -= n;       swap(l, L);       swap(r, R);       int lc = lca(l, r);       st ret = merge(go(l, dep[l] - dep[lc] + 1), go(r, dep[r] - dep[lc]).flip());       printf( %lld n , ret.dp[L >= n][R >= n]);     }     return 0;   }   