LOJ #145. DFS 序 2

#include <bits/stdc++.h>
#define
#define

using namespace std;
typedef long long ll;
ll w[A]; int pre[A], n, m, r;
int dfn[A], siz[A], fa[A], dep[A], cnt;
namespace Seg {
  struct node {int l, r; ll w, f;}tree[A << 2];
  void build(int k, int l, int r) {
    tree[k].l = l; tree[k].r = r;
    if (l == r) {tree[k].w = w[pre[l]]; tree[k].f = 0; return;}
    int m = (l + r) >> 1;
    build(k << 1, l, m); build(k << 1 | 1, m + 1, r);
    tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;
  }
  void down(int k) {
    tree[k << 1].f += tree[k].f; tree[k << 1 | 1].f += tree[k].f;
    tree[k << 1].w += 1LL * (tree[k << 1].r - tree[k << 1].l + 1) * tree[k].f;
    tree[k << 1 | 1].w += 1LL * (tree[k << 1 | 1].r - tree[k << 1 | 1].l + 1) * tree[k].f;
    tree[k].f = 0;
  }
  void change(int k, int l, int r, ll val) {
    if (tree[k].l >= l and tree[k].r <= r) {
      tree[k].w += 1LL * (tree[k].r - tree[k].l + 1) * val;
      tree[k].f += val; return;
    }
    int m = (tree[k].l + tree[k].r) >> 1;
    if (tree[k].f) down(k);
    if (l <= m) change(k << 1, l, r, val);
    if (r > m) change(k << 1 | 1, l, r, val);
    tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;
  }
  ll ask(int k, int l, int r) {
    if (tree[k].l >= l and tree[k].r <= r) return tree[k].w;
    if (tree[k].f) down(k);
    int m = (tree[k].l + tree[k].r) >> 1; ll ans = 0;
    if (l <= m) ans += ask(k << 1, l, r);
    if (r > m) ans += ask(k << 1 | 1, l, r);
    return ans;
  }
}
struct node {int next, to;}e[A << 1];
int head[A], num;
void add(int fr, int to) {e[++num].next = head[fr]; e[num].to = to; head[fr] = num;}
void prepare(int fr) {
  siz[fr] = 1; dfn[fr] = ++cnt, pre[cnt] = fr;
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (ca == fa[fr]) continue;
    fa[ca] = fr; prepare(ca); siz[fr] += siz[ca];
  }
}

int main(int argc, char const *argv[]) {
  cin >> n >> m >> r;
  for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
  for (int i = 2, a, b; i <= n; i++) scanf("%d%d", &a, &b), add(a, b), add(b, a);
  prepare(r); Seg::build(1, 1, n);
  while (m--) {
    int opt, a; ll x; scanf("%d%d", &opt, &a);
    if (opt == 1) scanf("%lld", &x), Seg::change(1, dfn[a], dfn[a] + siz[a] - 1, x);
    else printf("%lld\n", Seg::ask(1, dfn[a], dfn[a] + siz[a] - 1));
  }
  return 0;
}