求和

显然这就是一个树链剖分板子题

code

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

#define N 1000010
#define M 1010
#define lson rt << 1
#define rson rt << 1 | 1
#define int long long

using namespace std;
int n, m, cnt, k;
int dep[N], dfn[N], fa[N], son[N], pre[N], siz[N], top[N], w[N];

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

namespace Seg {
    struct Tree {
        int sum, len, lazy;
    }tree[N << 1];
    void push_up(int rt) {
        tree[rt].sum = tree[lson].sum + tree[rson].sum;
    }
    void build(int rt, int l, int r) {
        tree[rt].len = r - l + 1;
        if (l == r) {
            tree[rt].sum = w[pre[l]];
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        push_up(rt);
    }
    void push_down(int rt) {
        if (!tree[rt].sum) return;
        tree[lson].sum += tree[rt].lazy * tree[lson].len;
        tree[rson].sum += tree[rt].lazy * tree[rson].len;
        tree[lson].lazy += tree[rt].lazy;
        tree[rson].lazy += tree[rt].lazy;
        tree[rt].lazy = 0;
    }
    void updata(int rt, int c, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            tree[rt].sum += tree[rt].len * c;
            tree[rt].lazy += c;
            return;
        }
        push_down(rt);
        int mid = (l + r) >> 1;
        if (L <= mid) updata(lson, c, l, mid, L, R);
        if (R > mid) updata(rson, c, mid + 1, r, L, R);
        push_up(rt);
    }
    int query(int rt, int l, int r, int L, int R) {
        if (L <= l && r <= R) return tree[rt].sum;
        push_down(rt);
        int mid = (l + r) >> 1, ans = 0;
        if (L <= mid) ans += query(lson, l, mid, L, R);
        if (R > mid) ans += query(rson, mid + 1, r, L, R);
        return ans;
    }
}

namespace Cut {
    int head[N << 1], add_edge;
    struct node {
        int next, to;
    }edge[N << 1];
    void add(int from, int to) {
        edge[++add_edge].next = head[from];
        edge[add_edge].to = to;
        head[from] = add_edge;
    }
    void dfs(int x, int fath) {
        dep[x] = dep[fath] + 1, fa[x] = fath, siz[x] = 1;
        for (int i = head[x]; i; i = edge[i].next) {
            int to = edge[i].to;
            if (to == fath) continue;
            dfs(to, x);
            siz[x] += siz[to];
            if (siz[to] > siz[son[x]]) son[x] = to;
        }
    }
    void dfs2(int x, int tp) {
        dfn[x] = ++cnt, pre[cnt] = x, top[x] = tp;
        if (son[x]) dfs2(son[x], tp);
        for (int i = head[x]; i; i = edge[i].next) {
            int to = edge[i].to;
            if (to == son[x] || to == fa[x]) continue;
            dfs2(to, to); 
        }
    }
    void change(int x, int y, int c) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            Seg::updata(1, c, 1, n, dfn[top[x]], dfn[x]);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) swap(x, y);
        Seg::updata(1, c, 1, n, dfn[x], dfn[y]);
    }
    int asksum(int x, int y) {
        int ans = 0;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            ans += Seg::query(1, 1, n, dfn[top[x]], dfn[x]);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) swap(x, y);
        ans += Seg::query(1, 1, n, dfn[x], dfn[y]);
        return ans;
    }
}

signed main() {
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; i++) w[i] = read();
    for (int i = 1, x, y; i <= n - 1; i++) 
        x = read(), y = read(), Cut::add(x, y), Cut::add(y, x);
    Cut::dfs(k, 0), Cut::dfs2(k, 1), Seg::build(1, 1, n);
    for (int i = 1, opt, x, y; i <= m; i++) {
        opt = read();
        if (opt == 1) x = read(), y = read(), Cut::change(x, x, y);
        if (opt == 2) {
            x = read();
            printf("%d\n", Seg::query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1));
        }
    }
}