代码

#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 BLOCK_SIZE 8
#define MAX_BLOCKS ((MAX_N + BLOCK_SIZE - 1) / BLOCK_SIZE)
#define BLOCK_LOG 14
#define INF (1LL << 60)

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

static int head[MAX_N], edge_to[MAX_N * 2], edge_next[MAX_N * 2];
static int order[MAX_N], parent[MAX_N], depth[MAX_N];
static int subtree[MAX_N], heavy[MAX_N], chain_head[MAX_N];
static int position[MAX_N], node_at[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 edge_matrix[MAX_N];
static Matrix prefix_down[MAX_N], suffix_up[MAX_N];
static Matrix block_value[MAX_BLOCKS], block_table[BLOCK_LOG][MAX_BLOCKS];
static int block_count;

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 Matrix identity_matrix(void) {
    Matrix z = {0, INF, INF, 0};
    return z;
}

/* Ordered product over the reversed block array, inclusive. */
static __attribute__((always_inline)) inline Matrix block_range(int left, int right) {
    if (left == right) return block_value[left];
    unsigned difference = (unsigned)(left ^ right);
    int level = 31 - __builtin_clz(difference);
    return multiply(block_table[level][left], block_table[level][right]);
}

/* Product M[high] M[high-1] ... M[low] on one heavy chain. */
static __attribute__((always_inline)) inline Matrix position_range(int low, int high) {
    int low_block = low / BLOCK_SIZE;
    int high_block = high / BLOCK_SIZE;
    if (low_block == high_block) {
        Matrix result = edge_matrix[node_at[high]];
        for (int p = high - 1; p >= low; --p)
            result = multiply(result, edge_matrix[node_at[p]]);
        return result;
    }
    Matrix result = prefix_down[high];
    if (low_block + 1 < high_block) {
        int reverse_left = block_count - high_block;
        int reverse_right = block_count - 2 - low_block;
        result = multiply(result, block_range(reverse_left, reverse_right));
    }
    return multiply(result, suffix_up[low]);
}

static __attribute__((always_inline)) inline int tree_lca(int u, int v) {
    while (chain_head[u] != chain_head[v]) {
        if (depth[chain_head[u]] > depth[chain_head[v]]) u = parent[chain_head[u]];
        else v = parent[chain_head[v]];
    }
    return depth[u] < depth[v] ? u : v;
}

static __attribute__((always_inline)) inline Vector climb_forced(
        int u, int ancestor, int forced) {
    Vector value;
    if (forced) { value.v0 = INF; value.v1 = down1[u]; }
    else { value.v0 = down0[u]; value.v1 = INF; }

    Matrix path = identity_matrix();
    while (chain_head[u] != chain_head[ancestor]) {
        int top = chain_head[u];
        path = multiply(path, position_range(position[top], position[u]));
        u = parent[top];
    }
    if (u != ancestor)
        path = multiply(path, position_range(position[ancestor] + 1, position[u]));

    Vector result;
    result.v0 = min2(value.v0 + path.a00, value.v1 + path.a10);
    result.v1 = min2(value.v0 + path.a01, value.v1 + path.a11);
    return result;
}

static void build_range_products(int n) {
    block_count = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
    for (int block = 0; block < block_count; ++block) {
        int first = block * BLOCK_SIZE;
        int last = first + BLOCK_SIZE - 1;
        if (last >= n) last = n - 1;

        prefix_down[first] = edge_matrix[node_at[first]];
        for (int p = first + 1; p <= last; ++p)
            prefix_down[p] = multiply(edge_matrix[node_at[p]], prefix_down[p - 1]);
        suffix_up[last] = edge_matrix[node_at[last]];
        for (int p = last - 1; p >= first; --p)
            suffix_up[p] = multiply(suffix_up[p + 1], edge_matrix[node_at[p]]);

        /* Reverse block numbering makes an upward path an ascending query. */
        block_value[block_count - 1 - block] = prefix_down[last];
    }

    for (int level = 0; level < BLOCK_LOG; ++level) {
        int half = 1 << level;
        int span = half + half;
        for (int first = 0; first < block_count; first += span) {
            int middle = first + half;
            if (middle > block_count) middle = block_count;
            int last = first + span;
            if (last > block_count) last = block_count;
            if (middle > first) {
                block_table[level][middle - 1] = block_value[middle - 1];
                for (int p = middle - 2; p >= first; --p)
                    block_table[level][p] = multiply(block_value[p], block_table[level][p + 1]);
            }
            if (middle < last) {
                block_table[level][middle] = block_value[middle];
                for (int p = middle + 1; p < last; ++p)
                    block_table[level][p] = multiply(block_table[level][p - 1], block_value[p]);
            }
        }
    }
}

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 == parent[u]) continue;
            parent[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];
        int best_size = 0;
        subtree[u] = 1;
        for (int q = head[u]; q; q = edge_next[q - 1]) {
            int v = edge_to[q - 1];
            if (parent[v] != u) continue;
            a0 += down1[v];
            a1 += min2(down0[v], down1[v]);
            subtree[u] += subtree[v];
            if (subtree[v] > best_size) {
                best_size = subtree[v];
                heavy[u] = v;
            }
        }
        down0[u] = a0;
        down1[u] = a1;
    }

    outside0[1] = kind == 1 ? INF : 0;
    outside1[1] = 0;
    edge_matrix[1] = identity_matrix();
    for (int i = 1; i < n; ++i) {
        int v = order[i];
        int u = parent[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;
        edge_matrix[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) {
        int next_position = 0;
        for (int i = 0; i < n; ++i) {
            int start = order[i];
            if (start != 1 && heavy[parent[start]] == start) continue;
            for (int u = start; u; u = heavy[u]) {
                chain_head[u] = start;
                position[u] = next_position;
                node_at[next_position++] = u;
            }
        }
        build_range_products(n);
    }

    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 (parent[b] == a) {
                child = b; child_state = y; parent_state = x;
            } else {
                child = a; child_state = x; parent_state = y;
            }
            Matrix z = edge_matrix[child];
            long long child_cost = child_state ? down1[child] : down0[child];
            int p = parent[child];
            long long parent_out = parent_state ? outside1[p] : outside0[p];
            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, a, y);
                answer = x ? right.v1 + outside1[a] : right.v0 + outside0[a];
            } else if (common == b) {
                Vector left = climb_forced(a, b, x);
                answer = y ? left.v1 + outside1[b] : left.v0 + outside0[b];
            } else {
                Vector left = climb_forced(a, common, x);
                Vector right = climb_forced(b, 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

评测结果