C++ 解法, 执行用时: 2185ms, 内存消耗: 103484K, 提交时间: 2021-07-09 12:16:35

/**
 * Author: yurzhang
 * Date: 2021/07/09
 */
#include <cstdio>

#define gc (pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++)

const int N = 1000010;
const int MAXN = 2097162;
static char buf[100000], *pa = buf, *pb = buf;
inline int read() {
    int x = 0; char c = gc;
    while (c < '0' || c > '9') c = gc;
    while (c >= '0' && c <= '9')
        x = x * 10 + c - 48, c = gc;
    return x;
}

inline int lowbit(int x) {
    return x & -x;
}

int tot, stack[10], top;
inline int newNode() {
    if (top)
        return stack[top --];
    else return ++ tot;
}

int root[N], val[N], lc[N], rc[N], siz[N];
inline void up(int x) {
    siz[x] = siz[lc[x]] + siz[rc[x]] + 1;
}
inline void lr(int &x) {
    int y = rc[x];
    rc[x] = lc[y];
    lc[y] = x;
    siz[y] = siz[x];
    up(x); x = y;
}
inline void rr(int &x) {
    int y = lc[x];
    lc[x] = rc[y];
    rc[y] = x;
    siz[y] = siz[x];
    up(x); x = y;
}
inline void maintain(int &x, bool y) {
    if (y) {
        if (siz[rc[rc[x]]] > siz[lc[x]]) lr(x);
        else if (siz[lc[rc[x]]] > siz[lc[x]])
            rr(rc[x]), lr(x);
        else return;
    } else {
        if (siz[lc[lc[x]]] > siz[rc[x]]) rr(x);
        else if (siz[rc[lc[x]]] > siz[rc[x]])
            lr(lc[x]), rr(x);
        else return;
    } maintain(lc[x], false);
    maintain(rc[x], true);
    maintain(x, true);
    maintain(x, false);
}
void insert(int &now, int v) {
    if (now == 0) {
        now = newNode();
        val[now] = v;
        siz[now] = 1;
        lc[now] = rc[now] = 0;
    } else {
        ++ siz[now];
        if (val[now] <= v) {
            insert(rc[now], v);
            maintain(now, true);
        } else {
            insert(lc[now], v);
            maintain(now, false);
        }
    }
}
void erase(int &now, int v) {
    -- siz[now];
    if (val[now] == v) {
        if (lc[now] == 0 || rc[now] == 0) {
            stack[++ top] = now;
            now = lc[now] + rc[now];
        } else {
            int tmp = rc[now];
            while (lc[tmp]) tmp = lc[tmp];
            val[now] = val[tmp];
            erase(rc[now], val[tmp]);
        }
    } else if (val[now] < v)
        erase(rc[now], v);
    else erase(lc[now], v);
}
inline int getKth(int root, int k) {
    int now = root;
    while (now) {
        if (siz[lc[now]] + 1 == k)
            return val[now];
        if (siz[lc[now]] < k) {
            k -= siz[lc[now]] + 1;
            now = rc[now];
        } else now = lc[now];
    } return -1;
}

int n, m, v[N], nv[N], wt[N];
int opt, x, y, z;

inline void _add(int x, int v) {
    while (x <= n) {
        wt[x] += v;
        x += lowbit(x);
    }
}

inline void add(int l, int r, int v) {
    _add(l, v); _add(r + 1, -v);
}

inline int get(int x) {
    int res = 0;
    while (x) {
        res += wt[x];
        x -= lowbit(x);
    } return res;
}

int e, bg[N], nx[N << 1], to[N << 1];
inline void link(int u, int v) {
    to[++ e] = v;
    nx[e] = bg[u];
    bg[u] = e;
}

int fa[N], dep[N], ws[N], sz[N];
void dfs1(int now, int f) {
    fa[now] = f;
    dep[now] = dep[f] + 1;
    sz[now] = 1;
    int mx = -1;
    for (int i = bg[now]; i; i = nx[i])
        if (to[i] != f) {
            dfs1(to[i], now);
            sz[now] += sz[to[i]];
            if (sz[to[i]] > mx) {
                mx = sz[to[i]];
                ws[now] = to[i];
            }
        }
}

int cnt, tp[N], id[N];
void dfs2(int now, int top) {
    tp[now] = top;
    id[now] = ++ cnt;
    nv[cnt] = v[now];
    if (ws[now] == 0)
        return;
    dfs2(ws[now], top);
    for (int i = bg[now]; i; i = nx[i])
        if (to[i] != fa[now] && to[i] != ws[now]) {
            dfs2(to[i], to[i]);
            insert(root[now], v[to[i]]);
        }
}

inline void check(int x, int v) {
    if (x == tp[x] && fa[x]) {
        erase(root[fa[x]], get(id[x]));
        insert(root[fa[x]], get(id[x]) + v);
    }
}

void modify(int x, int y, int v) {
    while (tp[x] != tp[y]) {
        if (dep[tp[x]] > dep[tp[y]]) {
            check(tp[x], v);
            add(id[tp[x]], id[x], v);
            x = fa[tp[x]];
        } else {
            check(tp[y], v);
            add(id[tp[y]], id[y], v);
            y = fa[tp[y]];
        }
    } if (dep[x] > dep[y]) {
        check(y, v);
        add(id[y], id[x], v);
    } else {
        check(x, v);
        add(id[x], id[y], v);
    }
}

int query(int x, int y) {
    insert(root[x], get(id[x]));
    if (ws[x])
        insert(root[x], get(id[ws[x]]));
    if (fa[x])
        insert(root[x], get(id[fa[x]]));
    int res = getKth(root[x], y);
    erase(root[x], get(id[x]));
    if (ws[x])
        erase(root[x], get(id[ws[x]]));
    if (fa[x])
        erase(root[x], get(id[fa[x]]));
    return res;
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; ++ i)
        v[i] = read();
    for (int i = 1; i < n; ++ i) {
        x = read(); y = read();
        link(x, y); link(y, x);
    } dfs1(1, 0); dfs2(1, 1);
    for (int i = 1; i <= n; ++ i)
        _add(i, nv[i] - nv[i - 1]);
    while (m --) {
        opt = read(); x = read(); y = read();
        if (opt == 1) {
            z = read();
            modify(x, y, z);
        } else printf("%d\n", query(x, y));
    } return 0;
}