func_code_string: #include <bits/stdc++.h>   using namespace std;   #pragma warning(disable : 4996)   struct E {     int to;     vector<long long> w;   };   const long long INF = 1e18;   const int N = 3e5 + 5, L = 20;   vector<E> g[N];   long long t[N], d[2][2][N][L];   int anc[N][L], tin[N], tout[N];   int timer = 0, n;   void deep(int node) {     for (E e : g[node]) {       if (e.to != anc[node][0]) {         anc[e.to][0] = node;         deep(e.to);         t[node] = min(t[node], t[e.to] + e.w[0] + e.w[1]);       }     }   }   void walk(int node, long long u) {     u = min(u, t[node]);     t[node] = u;     for (E e : g[node]) {       if (e.to != anc[node][0]) walk(e.to, u + e.w[0] + e.w[1]);     }   }   void dfs(int node) {     tin[node] = timer++;     for (int i = 1; i < L; i++) {       anc[node][i] = anc[anc[node][i - 1]][i - 1];       for (int x = 0; x < 2; x++) {         for (int y = 0; y < 2; y++) {           for (int z = 0; z < 2; z++) {             d[x][z][node][i] =                 min(d[x][z][node][i],                     d[x][y][node][i - 1] + d[y][z][anc[node][i - 1]][i - 1]);           }         }       }     }     for (E e : g[node]) {       if (e.to != anc[node][0]) {         anc[e.to][0] = node;         for (int i = 0; i < 2; i++) {           d[i][i][e.to][0] = min(e.w[i], e.w[1 - i] + t[node] + t[e.to]);           d[i][1 - i][e.to][0] = min(e.w[1 - i] + t[e.to], t[node] + e.w[i]);         }         dfs(e.to);       }     }     tout[node] = timer;   }   bool upper(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }   long long calc(int x, int a, int y, int b) {     long long dp[2];     dp[x] = 0;     dp[1 - x] = t[a];     if (a == b) return dp[y];     for (int i = L - 1; i >= 0; i--) {       if (!upper(anc[a][i], b)) {         long long ndp[2] = {INF, INF};         for (int j = 0; j < 2; j++) {           for (int k = 0; k < 2; k++) {             ndp[k] = min(ndp[k], dp[j] + d[j][k][a][i]);           }         }         for (int j = 0; j < 2; j++) dp[j] = ndp[j];         a = anc[a][i];       }     }     return min(dp[0] + d[0][y][a][0], dp[1] + d[1][y][a][0]);   }   int getLca(int a, int b) {     if (upper(a, b)) return a;     for (int i = L - 1; i >= 0; i--) {       if (!upper(anc[a][i], b)) a = anc[a][i];     }     return anc[a][0];   }   long long getAns(int a, int b) {     int x = a % 2, y = b % 2;     a /= 2;     b /= 2;     int l = getLca(a, b);     long long ans = min(calc(x, a, 0, l) + calc(y, b, 0, l),                         calc(x, a, 1, l) + calc(y, b, 1, l));     return ans;   }   signed main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cin >> n;     for (int i = 0; i < n; i++) {       cin >> t[i];     }     for (int i = 0; i < n - 1; i++) {       int x, y;       long long w1, w2;       cin >> x >> y >> w1 >> w2;       x--, y--;       g[x].push_back({y, {w1, w2}});       g[y].push_back({x, {w1, w2}});     }     for (int i = 0; i < 2; i++) {       for (int j = 0; j < 2; j++) {         for (int k = 0; k < n; k++) {           for (int h = 0; h < L; h++) {             d[i][j][k][h] = INF;           }         }       }     }     deep(0);     walk(0, INF);     dfs(0);     int q;     cin >> q;     while (q--) {       int a, b;       cin >> a >> b;       a--, b--;       cout << getAns(a, b) <<   n ;     }     return 0;   }   