代码

#include <sys/auxv.h>
#include <stdint.h>

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

#define AT_DUCK 0x6b637564UL
#define INF 1000000000000000000LL

static int head[100005], to[200005], nxt[200005]; static int ecnt;
static long long pw[100005];
static int parent[100005], depth[100005], order[100005];
static long long f[100005][2], g[100005][2];
static int sz[100005], heavy[100005], hhead[100005], mp[100005], posNode[100005];
static long long seg[262144][2][2];
static int SZ;
static int n;

static inline long long mn(long long a, long long b){ return a < b ? a : b; }

static inline int rd(const char*& p){
  int x = 0;
  while (*p < '0' || *p > '9') ++p;
  while (*p >= '0' && *p <= '9') { x = x*10 + (*p - '0'); ++p; }
  return x;
}

static inline void exitasm(){
#ifdef DUCK_RENAME_MAIN
  return;
#else
  __asm__ __volatile__("mov $60, %%rax; xor %%rdi, %%rdi; syscall" ::: "rax","rdi","rcx","r11","memory");
#endif
}

static inline void add_edge(int u, int v){
  to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
}

static inline void mmul(long long C[2][2], const long long A[2][2], const long long B[2][2]){
  long long a00=A[0][0], a01=A[0][1], a10=A[1][0], a11=A[1][1];
  long long b00=B[0][0], b01=B[0][1], b10=B[1][0], b11=B[1][1];
  C[0][0] = mn(a00+b00, a01+b10);
  C[0][1] = mn(a00+b01, a01+b11);
  C[1][0] = mn(a10+b00, a11+b10);
  C[1][1] = mn(a10+b01, a11+b11);
}

static inline void ident(long long M[2][2]){
  M[0][0]=0; M[0][1]=INF; M[1][0]=INF; M[1][1]=0;
}

// ascending product over seg leaves [l, r] (1-indexed). l>r => identity.
static inline void qseg(long long res[2][2], int l, int r){
  if(l > r){ ident(res); return; }
  long long L[2][2], R[2][2];
  ident(L); ident(R);
  int lo = l-1+SZ, hi = r-1+SZ;
  while(lo <= hi){
    if(lo & 1){ long long t[2][2]; mmul(t, L, seg[lo]); L[0][0]=t[0][0];L[0][1]=t[0][1];L[1][0]=t[1][0];L[1][1]=t[1][1]; lo++; }
    if(!(hi & 1)){ long long t[2][2]; mmul(t, seg[hi], R); R[0][0]=t[0][0];R[0][1]=t[0][1];R[1][0]=t[1][0];R[1][1]=t[1][1]; hi--; }
    lo >>= 1; hi >>= 1;
  }
  mmul(res, L, R);
}

// descending product from y (deeper) up to x (shallower), exclusive of x.
// x,y in same chain. Returns T[y] (x) ... (x) T[child_of_x].
static inline void exclmat(int x, int y, long long M[2][2]){
  if(mp[y] <= mp[x]){ ident(M); return; }
  qseg(M, n - mp[y], n - mp[x] - 1);
}

// descending product from y (deeper) up to x (shallower), inclusive of x.
static inline void fullmat(int x, int y, long long M[2][2]){
  if(mp[y] < mp[x]){ ident(M); return; }
  qseg(M, n - mp[y], n - mp[x]);
}

static inline void applyM(long long& v0, long long& v1, const long long M[2][2]){
  long long n0 = mn(v0 + M[0][0], v1 + M[1][0]);
  long long n1 = mn(v0 + M[0][1], v1 + M[1][1]);
  v0 = n0; v1 = n1;
}

#ifdef DUCK_RENAME_MAIN
extern "C" int duck_solve()
#else
int main()
#endif
{
  struct DuckInfo *di = (struct DuckInfo *)getauxval(AT_DUCK);
  const char *p = di->stdin_ptr;
  n = rd(p); int mq = rd(p);
  while(*p==' '||*p=='\t'||*p=='\r') ++p;
  while(*p && *p!=' ' && *p!='\t' && *p!='\n' && *p!='\r') ++p;

  for(int i=1;i<=n;i++) pw[i] = rd(p);

  ecnt = 0;
  for(int i=1;i<n;i++){
    int u = rd(p), v = rd(p);
    add_edge(u,v); add_edge(v,u);
  }

  // BFS order + parent + depth (root = 1)
  int qhead = 0, qtail = 0;
  order[qtail++] = 1; parent[1] = 0; depth[1] = 0;
  while(qhead < qtail){
    int u = order[qhead++];
    for(int e=head[u]; e; e=nxt[e]){
      int v = to[e];
      if(v == parent[u]) continue;
      parent[v] = u; depth[v] = depth[u] + 1; order[qtail++] = v;
    }
  }

  // subtree DP f (bottom-up)
  for(int i=n-1;i>=0;i--){
    int u = order[i];
    long long s0 = 0, s1 = pw[u];
    for(int e=head[u]; e; e=nxt[e]){
      int v = to[e];
      if(v == parent[u]) continue;
      s0 += f[v][1];
      s1 += mn(f[v][0], f[v][1]);
    }
    f[u][0] = s0; f[u][1] = s1;
  }

  // complement DP g (top-down)
  g[1][0] = 0; g[1][1] = 0;
  for(int i=0;i<n;i++){
    int u = order[i];
    for(int e=head[u]; e; e=nxt[e]){
      int v = to[e];
      if(v == parent[u]) continue;
      long long mc = mn(f[v][0], f[v][1]);
      g[v][0] = g[u][1] + f[u][1] - mc;
      g[v][1] = mn(g[u][0] + f[u][0] - f[v][1], g[u][1] + f[u][1] - mc);
    }
  }

  // heavy-light decomposition
  for(int i=n-1;i>=0;i--){
    int u = order[i];
    sz[u] = 1; heavy[u] = 0;
    int best = 0;
    for(int e=head[u]; e; e=nxt[e]){
      int v = to[e];
      if(v == parent[u]) continue;
      sz[u] += sz[v];
      if(sz[v] > best){ best = sz[v]; heavy[u] = v; }
    }
  }
  int cur = 0;
  for(int i=0;i<n;i++){
    int u = order[i];
    if(parent[u]==0 || heavy[parent[u]] != u){
      int x = u;
      while(x != 0){ hhead[x] = u; mp[x] = cur; posNode[cur] = x; cur++; x = heavy[x]; }
    }
  }

  // segment tree over reversed M; M[j] = base matrix of node with mp = j-1
  SZ = 1;
  while(SZ < n) SZ <<= 1;
  for(int L=0; L<n; L++){
    int u = posNode[n-1-L]; // leaf L holds Mrev[L+1] = M[n-L] => node with mp = n-L-1
    long long *s = &seg[SZ+L][0][0];
    if(parent[u] == 0){
      s[0]=0; s[1]=INF; s[2]=INF; s[3]=0;
    } else {
      int pu = parent[u];
      long long h0 = f[pu][0] - f[u][1];
      long long h1 = f[pu][1] - mn(f[u][0], f[u][1]);
      s[0]=INF; s[1]=h1; s[2]=h0; s[3]=h1;
    }
  }
  for(int i=n;i<SZ;i++){
    long long *s = &seg[SZ+i][0][0];
    s[0]=0; s[1]=INF; s[2]=INF; s[3]=0;
  }
  for(int i=SZ-1;i>=1;i--) mmul(seg[i], seg[i<<1], seg[i<<1|1]);

  char *o = di->stdout_ptr;

  for(int qi=0; qi<mq; qi++){
    int a = rd(p), xa = rd(p), b = rd(p), xb = rd(p);

    // LCA via HLD
    int u = a, v = b;
    while(hhead[u] != hhead[v]){
      if(depth[hhead[u]] > depth[hhead[v]]) u = parent[hhead[u]];
      else v = parent[hhead[v]];
    }
    int L = (depth[u] < depth[v]) ? u : v;

    // lift a -> L
    long long Va0 = (xa==0)?0:INF, Va1 = (xa==1)?0:INF;
    u = a;
    while(hhead[u] != hhead[L]){
      long long M[2][2]; fullmat(hhead[u], u, M); applyM(Va0, Va1, M);
      u = parent[hhead[u]];
    }
    { long long M[2][2]; exclmat(L, u, M); applyM(Va0, Va1, M); }

    // lift b -> L
    long long Vb0 = (xb==0)?0:INF, Vb1 = (xb==1)?0:INF;
    v = b;
    while(hhead[v] != hhead[L]){
      long long M[2][2]; fullmat(hhead[v], v, M); applyM(Vb0, Vb1, M);
      v = parent[hhead[v]];
    }
    { long long M[2][2]; exclmat(L, v, M); applyM(Vb0, Vb1, M); }

    long long fac = f[a][xa], fbc = f[b][xb];
    long long best = INF;
    if(!((a==L && xa!=0) || (b==L && xb!=0))){
      long long c = Va0 + Vb0 - f[L][0] + fac + fbc + g[L][0];
      if(c < best) best = c;
    }
    if(!((a==L && xa!=1) || (b==L && xb!=1))){
      long long c = Va1 + Vb1 - f[L][1] + fac + fbc + g[L][1];
      if(c < best) best = c;
    }

    long long res = best;
    if(res > INF/2){
      *o++ = '-'; *o++ = '1';
    } else {
      char tmp[20]; int nn=0; long long vv = res;
      do { tmp[nn++] = (char)('0' + (vv % 10)); vv /= 10; } while(vv);
      while(nn) *o++ = tmp[--nn];
    }
    *o++ = '\n';
  }

  di->stdout_size = (uint64_t)(o - di->stdout_ptr);
  exitasm();
  return 0;
}

评测结果