代码

#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 const char DIG[] = "00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";

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 leaf[100005][2];
static long long segint[100005][2][2];
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){
  while (*p <= ' ') ++p;
  int x = *p++ - '0';
  while (*p >= '0' && *p <= '9') { x = x*10 + (*p++ - '0'); }
  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), used only in segment-tree build
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);
}

// reconstruct the 2x2 matrix of a segment-tree node (leaf or internal)
static inline void getmat(int node, long long M[2][2]){
  if(node >= n){
    int L = node - n;
    int u = posNode[n-1-L];
    if(parent[u] == 0){ M[0][0]=0; M[0][1]=INF; M[1][0]=INF; M[1][1]=0; }
    else { M[0][0]=INF; M[0][1]=leaf[L][1]; M[1][0]=leaf[L][0]; M[1][1]=leaf[L][1]; }
  } else {
    M[0][0]=segint[node][0][0]; M[0][1]=segint[node][0][1];
    M[1][0]=segint[node][1][0]; M[1][1]=segint[node][1][1];
  }
}

// apply a leaf (base matrix [INF,h1;h0,h1]) to vector
static inline void appleaf(long long& v0, long long& v1, int L){
  if(L == n-1) return; // root leaf = identity, never queried
  long long h0 = leaf[L][0], h1 = leaf[L][1];
  long long n0 = v1 + h0;
  long long n1 = mn(v0, v1) + h1;
  v0 = n0; v1 = n1;
}

// apply segment-tree node to vector [v0,v1]
static inline void appnode(long long& v0, long long& v1, int node){
  if(node >= n){ appleaf(v0, v1, node - n); return; }
  long long n0 = mn(v0 + segint[node][0][0], v1 + segint[node][1][0]);
  long long n1 = mn(v0 + segint[node][0][1], v1 + segint[node][1][1]);
  v0 = n0; v1 = n1;
}

// apply descending product over leaves [l, r] (1-indexed) to vector. l>r => no-op.
static inline void qdesc_vec(long long& v0, long long& v1, int l, int r){
  if(l > r) return;
  if(l == r){ appleaf(v0, v1, l-1); return; }
  int lo = l-1+n, hi = r+n;
  int stk[40]; int top = 0;
  while(lo < hi){
    if(lo & 1){ appnode(v0, v1, lo); lo++; }
    if(hi & 1){ hi--; stk[top++] = hi; }
    lo >>= 1; hi >>= 1;
  }
  while(top){ appnode(v0, v1, stk[--top]); }
}

// apply T[y] (x) ... (x) T[child_of_x] to vector (exclusive of x)
static inline void excl_vec(int x, int y, long long& v0, long long& v1){
  if(mp[y] <= mp[x]) return;
  qdesc_vec(v0, v1, n - mp[y], n - mp[x] - 1);
}

// apply T[y] (x) ... (x) T[x] to vector (inclusive of x)
static inline void full_vec(int x, int y, long long& v0, long long& v1){
  if(mp[y] < mp[x]) return;
  qdesc_vec(v0, v1, n - mp[y], n - mp[x]);
}

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

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

  for(int i=n-1;i>=0;i--){
    int u = order[i];
    long long s0 = 0, s1 = pw[u];
    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;
      s0 += f[v][1];
      s1 += mn(f[v][0], f[v][1]);
      sz[u] += sz[v];
      if(sz[v] > best){ best = sz[v]; heavy[u] = v; }
    }
    f[u][0] = s0; f[u][1] = s1;
  }

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

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

  for(int L=0; L<n; L++){
    int u = posNode[n-1-L];
    if(parent[u] == 0){ leaf[L][0]=0; leaf[L][1]=0; }
    else {
      int pu = parent[u];
      leaf[L][0] = f[pu][0] - f[u][1];
      leaf[L][1] = f[pu][1] - mn(f[u][0], f[u][1]);
    }
  }
  for(int i=n-1;i>=1;i--){
    long long A[2][2], B[2][2];
    getmat(i<<1, A);
    getmat(i<<1|1, B);
    mmul(segint[i], A, B);
  }

  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;
    while(hhead[u] != hhead[v]){
      if(depth[hhead[u]] > depth[hhead[v]]){
        full_vec(hhead[u], u, Va0, Va1);
        u = parent[hhead[u]];
      } else {
        full_vec(hhead[v], v, Vb0, Vb1);
        v = parent[hhead[v]];
      }
    }
    int L = (depth[u] < depth[v]) ? u : v;
    excl_vec(L, u, Va0, Va1);
    excl_vec(L, v, Vb0, Vb1);

    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[24]; int nn=0; long long vv = res;
      while(vv >= 100){
        int d = (int)(vv % 100); vv /= 100;
        tmp[nn++] = DIG[d*2+1]; tmp[nn++] = DIG[d*2];
      }
      if(vv >= 10){ tmp[nn++] = (char)('0' + (vv%10)); tmp[nn++] = (char)('0' + (vv/10)); }
      else tmp[nn++] = (char)('0' + vv);
      while(nn) *o++ = tmp[--nn];
    }
    *o++ = '\n';
  }

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

评测结果