代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


#define MAX_N 100005
#define LOG_N 17
#define INF (1LL << 60)

typedef struct {
    long long a00, a01, a10, a11;
} Matrix;

static int head[MAX_N], edge_to[MAX_N * 2], edge_next[MAX_N * 2];
static int order[MAX_N], depth[MAX_N];
static int ancestor[LOG_N][MAX_N];
static long long price[MAX_N], down0[MAX_N], down1[MAX_N];
static long long outside0[MAX_N], outside1[MAX_N];
static Matrix jump[LOG_N][MAX_N];

static __attribute__((always_inline)) inline long long min2(long long a, long long b) {
    return a < b ? a : b;
}

static __attribute__((always_inline)) inline Matrix multiply(Matrix x, Matrix y) {
    Matrix z;
    z.a00 = min2(x.a00 + y.a00, x.a01 + y.a10);
    z.a01 = min2(x.a00 + y.a01, x.a01 + y.a11);
    z.a10 = min2(x.a10 + y.a00, x.a11 + y.a10);
    z.a11 = min2(x.a10 + y.a01, x.a11 + y.a11);
    return z;
}

static __attribute__((always_inline)) inline int tree_lca(int u, int v) {
    if (depth[u] < depth[v]) { int t = u; u = v; v = t; }
    unsigned difference = (unsigned)(depth[u] - depth[v]);
    for (int k = 0; k < LOG_N; ++k)
        if (difference & (1U << k)) u = ancestor[k][u];
    if (u == v) return u;
    for (int k = LOG_N - 1; k >= 0; --k) {
        if (ancestor[k][u] != ancestor[k][v]) {
            u = ancestor[k][u];
            v = ancestor[k][v];
        }
    }
    return ancestor[0][u];
}

typedef struct { long long v0, v1; } Vector;

static __attribute__((always_inline)) inline Vector climb_forced(
        int u, unsigned distance, int forced) {
    Vector value;
    if (forced) { value.v0 = INF; value.v1 = down1[u]; }
    else { value.v0 = down0[u]; value.v1 = INF; }
    for (int k = 0; k < LOG_N; ++k) {
        if (distance & (1U << k)) {
            Matrix z = jump[k][u];
            Vector next;
            next.v0 = min2(value.v0 + z.a00, value.v1 + z.a10);
            next.v1 = min2(value.v0 + z.a01, value.v1 + z.a11);
            value = next;
            u = ancestor[k][u];
        }
    }
    return value;
}

static void solve(DuckInfo *info) {
    const char *in = info->stdin_ptr;
    int n = (int)duck_read_u64(&in);
    int query_count = (int)duck_read_u64(&in);
    while ((unsigned char)*in <= ' ') ++in;
    ++in; /* A, B, or C */
    int kind = *in - '0';
    while ((unsigned char)*in > ' ') ++in;

    for (int u = 1; u <= n; ++u) price[u] = (long long)duck_read_u64(&in);
    for (int i = 0; i < n - 1; ++i) {
        int u = (int)duck_read_u64(&in);
        int v = (int)duck_read_u64(&in);
        int e = i + i;
        edge_to[e] = v;
        edge_next[e] = head[u];
        head[u] = e + 1;
        edge_to[e + 1] = u;
        edge_next[e + 1] = head[v];
        head[v] = e + 2;
    }

    int order_size = 1;
    order[0] = 1;
    for (int i = 0; i < order_size; ++i) {
        int u = order[i];
        for (int q = head[u]; q; q = edge_next[q - 1]) {
            int v = edge_to[q - 1];
            if (v == ancestor[0][u]) continue;
            ancestor[0][v] = u;
            depth[v] = depth[u] + 1;
            order[order_size++] = v;
        }
    }

    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        long long a0 = 0, a1 = price[u];
        for (int q = head[u]; q; q = edge_next[q - 1]) {
            int v = edge_to[q - 1];
            if (ancestor[0][v] != u) continue;
            a0 += down1[v];
            a1 += min2(down0[v], down1[v]);
        }
        down0[u] = a0;
        down1[u] = a1;
    }

    outside0[1] = kind == 1 ? INF : 0;
    outside1[1] = 0;
    for (int i = 1; i < n; ++i) {
        int v = order[i];
        int u = ancestor[0][v];
        long long contribution0 = down1[v];
        long long contribution1 = min2(down0[v], down1[v]);
        Matrix z;
        z.a00 = INF;
        z.a01 = down1[u] - contribution1;
        z.a10 = down0[u] - contribution0;
        z.a11 = z.a01;
        jump[0][v] = z;
        outside0[v] = min2(z.a00 + outside0[u], z.a01 + outside1[u]);
        outside1[v] = min2(z.a10 + outside0[u], z.a11 + outside1[u]);
    }

    if (kind == 3) {
        for (int k = 1; k < LOG_N; ++k) {
            for (int u = 1; u <= n; ++u) {
                int middle = ancestor[k - 1][u];
                ancestor[k][u] = ancestor[k - 1][middle];
                jump[k][u] = multiply(jump[k - 1][u], jump[k - 1][middle]);
            }
        }
    }

    char *out = info->stdout_ptr;
    for (int qi = 0; qi < query_count; ++qi) {
        int a = (int)duck_read_u64(&in);
        int x = (int)duck_read_u64(&in);
        int b = (int)duck_read_u64(&in);
        int y = (int)duck_read_u64(&in);
        long long answer;

        if (kind == 1) {
            answer = y ? down1[b] + outside1[b] : down0[b] + outside0[b];
        } else if (kind == 2) {
            int child, child_state, parent_state;
            if (ancestor[0][b] == a) {
                child = b; child_state = y; parent_state = x;
            } else {
                child = a; child_state = x; parent_state = y;
            }
            Matrix z = jump[0][child];
            long long child_cost = child_state ? down1[child] : down0[child];
            int parent = ancestor[0][child];
            long long parent_out = parent_state ? outside1[parent] : outside0[parent];
            long long bridge;
            if (!child_state) bridge = parent_state ? z.a01 : z.a00;
            else bridge = parent_state ? z.a11 : z.a10;
            answer = child_cost + bridge + parent_out;
        } else {
            int common = tree_lca(a, b);
            if (common == a) {
                Vector right = climb_forced(b, (unsigned)(depth[b] - depth[a]), y);
                answer = (x ? right.v1 + outside1[a] : right.v0 + outside0[a]);
            } else if (common == b) {
                Vector left = climb_forced(a, (unsigned)(depth[a] - depth[b]), x);
                answer = (y ? left.v1 + outside1[b] : left.v0 + outside0[b]);
            } else {
                Vector left = climb_forced(a, (unsigned)(depth[a] - depth[common]), x);
                Vector right = climb_forced(b, (unsigned)(depth[b] - depth[common]), y);
                long long state0 = left.v0 + right.v0 - down0[common] + outside0[common];
                long long state1 = left.v1 + right.v1 - down1[common] + outside1[common];
                answer = min2(state0, state1);
            }
        }
        if (answer >= INF / 2) answer = -1;
        out = duck_write_i64(out, answer);
        *out++ = '\n';
    }
    info->stdout_size = (unsigned long)(out - info->stdout_ptr);
}

#ifndef LOCAL_VERIFY
__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    solve(duck_info(argc, argv));
    duck_exit();
}
int main(void) {}
#else
#include <stdio.h>
static char local_input[4 * 1024 * 1024];
static char local_output[2 * 1024 * 1024];
int main(void) {
    unsigned long length = fread(local_input, 1, sizeof(local_input), stdin);
    DuckInfo info = {0};
    info.stdin_ptr = local_input;
    info.stdin_size = length;
    info.stdout_ptr = local_output;
    solve(&info);
    fwrite(local_output, 1, info.stdout_size, stdout);
    return 0;
}
#endif

评测结果