代码

#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 LOG 17
#define INF 1000000000000000000LL

static int head[100005], to[200005], nxt[200005]; static int ecnt;
static int deg[100005];
static long long pw[100005];
static int parent[100005], depth[100005], order[100005];
static long long f[100005][2], g[100005][2];
static int fa[100005][LOG];
static long long W[LOG][100005][2][2];
static long long seg[262144][2][2];
static int SZ;

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;
}

// C = A (x) B  (min-plus)
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)
static inline void qseg(long long res[2][2], int l, int r){
  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);
}

#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;
  int n = rd(p), mq = rd(p);
  while(*p==' '||*p=='\t'||*p=='\r') ++p;
  while(*p && *p!=' ' && *p!='\t' && *p!='\n' && *p!='\r') ++p; // skip type string

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

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

  int is_path = 1;
  int root = 1;
  if(n >= 2){
    for(int i=1;i<=n;i++) if(deg[i] > 2){ is_path = 0; break; }
    if(is_path){
      for(int i=1;i<=n;i++) if(deg[i] == 1){ root = i; break; }
    }
  }

  // BFS order + parent + depth (root chosen)
  int qhead = 0, qtail = 0;
  order[qtail++] = root; parent[root] = 0; depth[root] = 0;
  int maxdepth = 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;
      if(depth[v] > maxdepth) maxdepth = depth[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[root][0] = 0; g[root][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);
    }
  }

  char *o = di->stdout_ptr;

  if(is_path){
    // segment tree over path order (root = endpoint => order[] is the path)
    SZ = 1;
    while(SZ < n) SZ <<= 1;
    // leaves: seg[SZ+i] = Mrev[i+1] = M[n-i]
    // M[j] (1-indexed): base matrix of order[j-1] (edge to order[j-2]); M[1]=identity
    // Mrev[i] = M[n+1-i]  => seg[SZ+i] = M[n-i] for i=0..n-1
    for(int i=0;i<n;i++){
      int j = n - i; // M index
      if(j == 1){
        seg[SZ+i][0][0]=0; seg[SZ+i][0][1]=INF;
        seg[SZ+i][1][0]=INF; seg[SZ+i][1][1]=0;
      } else {
        int u = order[j-1];
        int pu = order[j-2];
        long long h0 = f[pu][0] - f[u][1];
        long long h1 = f[pu][1] - mn(f[u][0], f[u][1]);
        seg[SZ+i][0][0]=INF; seg[SZ+i][0][1]=h1;
        seg[SZ+i][1][0]=h0;  seg[SZ+i][1][1]=h1;
      }
    }
    for(int i=n;i<SZ;i++){
      seg[SZ+i][0][0]=0; seg[SZ+i][0][1]=INF;
      seg[SZ+i][1][0]=INF; seg[SZ+i][1][1]=0;
    }
    for(int i=SZ-1;i>=1;i--) mmul(seg[i], seg[i<<1], seg[i<<1|1]);

    for(int qi=0; qi<mq; qi++){
      int a = rd(p), xa = rd(p), b = rd(p), xb = rd(p);
      int da = depth[a], db = depth[b];
      long long res;
      if(da < db){
        // a ancestor of b; lift(b,a) = product over M[da+2 .. db+1] descending
        // = ascending over Mrev[n-db .. n-da-1]
        long long pr[2][2];
        qseg(pr, n-db, n-da-1);
        res = f[b][xb] + pr[xb][xa] + g[a][xa];
      } else {
        long long pr[2][2];
        qseg(pr, n-da, n-db-1);
        res = f[a][xa] + pr[xa][xb] + g[b][xb];
      }
      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';
    }
  } else {
    // binary lifting
    for(int i=0;i<n;i++){
      int u = order[i];
      fa[u][0] = parent[u];
      if(parent[u] == 0){
        W[0][u][0][0]=0; W[0][u][0][1]=INF;
        W[0][u][1][0]=INF; W[0][u][1][1]=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]);
        W[0][u][0][0]=INF; W[0][u][0][1]=h1;
        W[0][u][1][0]=h0;  W[0][u][1][1]=h1;
      }
    }
    int lg = 1;
    while((1<<lg) <= maxdepth) lg++;
    for(int j=1;j<lg;j++){
      for(int u=1;u<=n;u++){
        int mid = fa[u][j-1];
        int anc = mid ? fa[mid][j-1] : 0;
        fa[u][j] = anc;
        if(anc == 0) continue;
        long long a00=W[j-1][u][0][0], a01=W[j-1][u][0][1], a10=W[j-1][u][1][0], a11=W[j-1][u][1][1];
        long long b00=W[j-1][mid][0][0], b01=W[j-1][mid][0][1], b10=W[j-1][mid][1][0], b11=W[j-1][mid][1][1];
        W[j][u][0][0] = mn(a00+b00, a01+b10);
        W[j][u][0][1] = mn(a00+b01, a01+b11);
        W[j][u][1][0] = mn(a10+b00, a11+b10);
        W[j][u][1][1] = mn(a10+b01, a11+b11);
      }
    }

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

      int u = a, v = b;
      long long Va0 = (xa==0)?0:INF, Va1 = (xa==1)?0:INF;
      long long Vb0 = (xb==0)?0:INF, Vb1 = (xb==1)?0:INF;

      if(depth[a] > depth[b]){
        int d = depth[a] - depth[b];
        for(int j=lg-1;j>=0;j--) if((d>>j)&1){
          long long n0 = mn(Va0 + W[j][u][0][0], Va1 + W[j][u][1][0]);
          long long n1 = mn(Va0 + W[j][u][0][1], Va1 + W[j][u][1][1]);
          Va0 = n0; Va1 = n1; u = fa[u][j];
        }
      } else if(depth[b] > depth[a]){
        int d = depth[b] - depth[a];
        for(int j=lg-1;j>=0;j--) if((d>>j)&1){
          long long n0 = mn(Vb0 + W[j][v][0][0], Vb1 + W[j][v][1][0]);
          long long n1 = mn(Vb0 + W[j][v][0][1], Vb1 + W[j][v][1][1]);
          Vb0 = n0; Vb1 = n1; v = fa[v][j];
        }
      }

      int L;
      if(u != v){
        for(int j=lg-1;j>=0;j--){
          if(fa[u][j] != fa[v][j]){
            long long n0 = mn(Va0 + W[j][u][0][0], Va1 + W[j][u][1][0]);
            long long n1 = mn(Va0 + W[j][u][0][1], Va1 + W[j][u][1][1]);
            Va0 = n0; Va1 = n1; u = fa[u][j];
            n0 = mn(Vb0 + W[j][v][0][0], Vb1 + W[j][v][1][0]);
            n1 = mn(Vb0 + W[j][v][0][1], Vb1 + W[j][v][1][1]);
            Vb0 = n0; Vb1 = n1; v = fa[v][j];
          }
        }
        long long n0 = mn(Va0 + W[0][u][0][0], Va1 + W[0][u][1][0]);
        long long n1 = mn(Va0 + W[0][u][0][1], Va1 + W[0][u][1][1]);
        Va0 = n0; Va1 = n1; u = fa[u][0];
        n0 = mn(Vb0 + W[0][v][0][0], Vb1 + W[0][v][1][0]);
        n1 = mn(Vb0 + W[0][v][0][1], Vb1 + W[0][v][1][1]);
        Vb0 = n0; Vb1 = n1; v = fa[v][0];
        L = u;
      } else {
        L = u;
      }

      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;
}

评测结果