代码

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

#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++){
    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);
    }
  }

  // binary lifting: fa and W matrices
  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];               // parent state 0, skip u
      long long h1 = f[pu][1] - mn(f[u][0], f[u][1]);  // parent state 1, skip u
      // W[u][0][i][j] = hang(parent,skip=u,j) + edge(i,j)
      // i=0 row:
      W[0][u][0][0] = INF;                    // edge(0,0) invalid
      W[0][u][0][1] = h1;                     // edge(0,1) ok, parent=1
      // i=1 row:
      W[0][u][1][0] = h0;                     // edge(1,0) ok, parent=0
      W[0][u][1][1] = h1;                     // edge(1,1) ok, parent=1
    }
  }
  for(int j=1;j<LOG;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; // W[j][u] never accessed by queries
      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);
    }
  }

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

    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;

    // align depths: lift deeper one, accumulating the path matrix
    if(depth[a] > depth[b]){
      int d = depth[a] - depth[b];
      for(int j=LOG-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=LOG-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=LOG-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;
}

评测结果