记录编号	416375	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	1.030 s
提交时间	2017-06-21 13:19:49	内存使用	7.81 MiB

# include <bits/stdc++.h>
# define mid ((l + r) >> 1)
# define MAXN 100023
using namespace std;

char buf[1 << 18], *fs, *ft;

inline char getc() { 
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline long long gn() { 
    register long long k = 0, f = 1;
    register char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}

struct edge { 
    long long to;
    edge *ne;
    edge() {;}
    edge(long long x, edge *y) { 
        to = x;
        ne = y;
    }
}*head[MAXN];

inline void addedge(long long fr, long long to) { 
    head[fr] = new edge(to, head[fr]);
    head[to] = new edge(fr, head[to]);
}

long long n, m, w[MAXN], a[MAXN];

long long fa[MAXN], dep[MAXN], son[MAXN], siz[MAXN], q[MAXN], l, r;

inline void bfs() { 
    q[1] = l = r = 1;
    while(l <= r) { 
        long long u = q[l++];
        siz[u] = 1;
        dep[u] = dep[fa[u]] + 1;
        for(edge *e = head[u]; e; e = e->ne) { 
            long long v = e->to;
            if(dep[v]) continue;
            fa[v] = u;
            q[++r] = v;
        }
    }
    for(long long i = r; i; i--) { 
        siz[fa[q[i]]] += siz[q[i]];
        if(siz[son[fa[q[i]]]] < siz[q[i]]) son[fa[q[i]]] = q[i];
    }
}

long long dfn[MAXN], id, top[MAXN];

void dfs(long long u, long long tp) { 
    dfn[u] = ++id;
    top[u] = tp;
    if(!son[u]) return;
    dfs(son[u], tp);
    for(edge *e = head[u]; e; e = e->ne) { 
        if(dfn[e->to]) continue;
        dfs(e->to, e->to);
    }
}

struct node { 
    long long sum, lz;
    node *ls, *rs;
    node(){;}
    inline void pu() { 
        sum = ((ls) ? ls->sum : 0) + ((rs) ? rs->sum : 0);
    }
    inline void pd(long long l, long long r) { 
        if(ls) { 
            ls->lz += lz;
            ls->sum += lz * (mid - l + 1);
        }
        if(rs) { 
            rs->lz += lz;
            rs->sum += lz * (r - mid);
        }
        lz = 0;
    }
} *root;

node *build(long long l, long long r) { 
    node *x = new node();
    if(l ^ r) { 
        x->ls = build(l, mid);
        x->rs = build(mid + 1, r);
        x->pu();
    } else { 
        x->sum = a[l];
    }
    return x;
}

void add(node *&x, long long l, long long r, long long s, long long t, long long p) { 
    x->pd(l, r);
    if(l == s && r == t) { 
        x->lz += p;
        x->sum += p * (r - l + 1);
    } else { 
        if(t <= mid) add(x->ls, l, mid, s, t, p);
        else if(s > mid) add(x->rs, mid + 1, r, s, t, p);
        else { 
            add(x->ls, l, mid, s, mid, p);
            add(x->rs, mid + 1, r, mid + 1, t, p);
        }
        x->pu();
    }
}

long long query(node *x, long long l, long long r, long long s, long long t) { 
    x->pd(l, r);
    if(l == s && r == t) { 
        return x->sum;
    } else {  
        if(t <= mid) return query(x->ls, l, mid, s, t);
        else if(s > mid) return query(x->rs, mid + 1, r, s, t);
        else { 
            return query(x->ls, l, mid, s, mid) + query(x->rs, mid + 1, r, mid + 1, t);
        }
    }
}

long long find(long long x) { 
# define tx top[x]
    long long ans = 0;
    while(x) { 
        ans += query(root, 1, n, dfn[tx], dfn[x]);
        x = fa[tx];
    }
    return ans;
}

int main() { 
# ifndef  LOCAL
    freopen("haoi2015_t2.in", "r", stdin);
    freopen("haoi2015_t2.out", "w", stdout);
# else 
    freopen("in", "r", stdin);
# endif
    n = gn(), m = gn();
    for(long long i = 1; i <= n; i++) w[i] = gn();
    for(long long i = 1; i < n; i++) addedge(gn(), gn());
    bfs();
    dfs(1, 1);
    for(long long i = 1; i <= n; i++) a[dfn[i]] = w[i];
    root = build(1, n);
    while(m--) { 
        long long op = gn();
        long long x = gn();
        if(op == 1) { 
            add(root, 1, n, dfn[x], dfn[x], gn());
        } else if(op == 2) {
            add(root, 1, n, dfn[x], dfn[x] + siz[x] - 1, gn());
        } else if(op == 3) { 
            printf("%lld\n", find(x));
        }
    }
}