记录编号	318161	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.981 s
提交时间	2016-10-08 22:05:38	内存使用	11.37 MiB

#include <cstdio>
#include <cstdarg>
#include <queue>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <cctype>
#define MAXN 100002
using namespace std;
typedef long long LL;
LL get_num()
{
    LL r;
    char c;
    bool sig = false;
    while(c = getchar())
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')sig = true;
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return sig? -r:r;
}
vector<int> G[MAXN];
int top[MAXN], parent[MAXN], deep[MAXN];
int son[MAXN], size[MAXN];
int post[MAXN];
int upost[MAXN];
int term[MAXN];
int hasid = 0;
void dfs(int u, int f, int d)
{
    size[u] = 1;
    parent[u] = f;
    deep[u] = d;
    son[u] = 0;
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != f)
        {
            dfs(to, u, d+1);
            size[u] += size[to];
            if(size[son[u]] < size[to])
                son[u] = to;
        }
    }
}
void dfs(int u, int tp)
{
    top[u] = tp;
    post[u] = ++hasid;
    upost[post[u]] = u;
    if(son[u])dfs(son[u], tp);
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != son[u] && to != parent[u])dfs(to, to);
    }
    term[u] = hasid;
}
LL val[MAXN];
struct node
{
    int l, r;
    int ls, rs;
    LL lazy;
    LL sum;
    void calc(LL d)
    {
        sum += (r-l+1)*d;
    }
}ns[MAXN<<1];
void pushup(node &d)
{
    d.sum = ns[d.ls].sum + ns[d.rs].sum;
}
int root = 1;
int last = root;
int build(int l, int r)
{
    if(l > r)return 0;
    int cur = last++;
    node &d = ns[cur];
    d.r = r;
    d.l = l;
    if(l == r)
        d.sum = val[upost[l]];
    else
    {
        int m = (l+r)>>1;
        d.ls = build(l, m);
        d.rs = build(m+1, r);
        pushup(d);
    }
    return cur;
}
void pushdown(node &d)
{
    ns[d.ls].lazy += d.lazy;
    ns[d.ls].calc(d.lazy);
    ns[d.rs].lazy += d.lazy;
    ns[d.rs].calc(d.lazy);
    d.lazy = 0;
}
LL querytree(int c, int l, int r)
{
    if(!c)return 0;
    node &d = ns[c];
    if(d.l == l && d.r == r)
        return d.sum;
    else
    {
        pushdown(d);
        if(l >= ns[d.rs].l)return querytree(d.rs, l, r);
        else if(r <= ns[d.ls].r)return querytree(d.ls, l, r);
        else return querytree(d.ls, l, ns[d.ls].r) + querytree(d.rs, ns[d.rs].l, r);
    }
}
void update(int c, int l, int r, LL v)
{
    if(!c)return;
    node &d = ns[c];
    if(d.l == l && d.r == r)
    {
        d.lazy += v;
        d.calc(v);
    }else
    {
        pushdown(d);
        if(l >= ns[d.rs].l)update(d.rs, l, r, v);
        else if(r <= ns[d.ls].r)update(d.ls, l, r, v);
        else
        {
            update(d.ls, l, ns[d.ls].r, v);
            update(d.rs, ns[d.rs].l, r, v);
        }
        pushup(d);
    }
}
void add1(int x, LL v)
{
    update(1, post[x], post[x], v);
}
void add2(int x, LL v)
{
    update(1, post[x], term[x], v);
}
LL query(int x)
{
    LL ans = 0;
    while(x != 0)
    {
        int t = top[x];
        int l = post[t];
        int r = post[x];
        ans += querytree(1, l, r);
        x = parent[t];
    }
    return ans;
}
int main()
{
    freopen("haoi2015_t2.in", "r", stdin);
    freopen("haoi2015_t2.out", "w", stdout);
    int n, m;
    n = (int)get_num();
    m = (int)get_num();
    for(int i = 1; i <= n; i++)val[i] = get_num();
    for(int i = 1; i < n; i++)
    {
        int a, b;
        a = (int)get_num();
        b = (int)get_num();
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1, 0, 1);
    dfs(1, 1);
    build(1, hasid);
    while(m--)
    {
        int op;
        op = (int)get_num();
        if(op == 1)
        {
            int x = (int)get_num();
            int v = get_num();
            add1(x, v);
        }else if(op == 2)
        {
            int x = (int)get_num();
            int v = get_num();
            add2(x, v);
        }else if(op == 3)
        {
            int x = (int)get_num();
            printf("%lld\n", query(x));
        }
    }
    return 0;
}