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

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const long long MAXN = 1e5 + 10;

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

inline long long in(void){
    register long long res = 0, f = 1;
    register char tmp = getc();
    while(!isdigit(tmp) && tmp ^ '-') tmp = getc();
    if(tmp == '-') f = -1, tmp = getc();
    while(isdigit(tmp))
        res = (res + (res << 2) << 1) + (tmp ^ 48),
        tmp = getc();
    return res * f;
}

struct EDGE{
    long long to;
    EDGE *ne;

    EDGE(){;}
    EDGE(long long _to, EDGE *_ne){
        to = _to, ne = _ne;
    }
};

struct NODE{
    long long sum, tag;
    NODE *ls, *rs;

    NODE(){
        ls = rs = NULL;
        tag = 0;
    }
};

inline void add_edge(long long fr, long long to);
void dfs(long long u);
void dfs(long long u, long long tp);
NODE* Build(long long l, long long r);
void update(NODE *node, long long l, long long r, long long k, long long L, long long R);
long long Query(NODE *node, long long l, long long r, long long L, long long R);

NODE *root;
EDGE *head[MAXN];
long long val[MAXN];
long long fa[MAXN], siz[MAXN];
long long top[MAXN], fat[MAXN];
long long dfn[MAXN], id[MAXN];
bool visit[MAXN];
long long opt, arg;
long long N, M;

int main(){ 
#ifndef LOCAL
    freopen("haoi2015_t2.in", "r", stdin);
    freopen("haoi2015_t2.out", "w", stdout);
#endif
    memset(visit, 0x00, sizeof(visit));

    N = in(), M = in();
    for(long long i = 1; i <= N; ++i) val[i] = in();
    for(long long i = 1; i < N; ++i){
        add_edge(in(), in());
    }

    dfs(1);
    dfs(1, 1);

    root = Build(1, N);

    for(long long i = 1; i <= M; ++i){
        opt = in(), arg = in();
        if(opt == 1) update(root, dfn[arg], dfn[arg], in(), 1, N);
        else if(opt == 2) update(root, dfn[arg], dfn[arg] + siz[arg] - 1, in(), 1, N);
        else if(opt == 3){
            register long long res = 0;
            register long long tp = top[arg];

            while(tp ^ 1){
                res += Query(root, dfn[tp], dfn[arg], 1, N);
                arg = fa[tp];
                tp = top[arg];
            }

            printf("%lld\n", Query(root, dfn[1], dfn[arg], 1, N) + res);
        }
    }

    return 0;
}

inline void add_edge(long long fr, long long to){
    static EDGE *edge;
    edge = new EDGE(to, head[fr]), head[fr] = edge;
    edge = new EDGE(fr, head[to]), head[to] = edge;
    return ;
}

void dfs(long long u){
    visit[u] = true;
    siz[u] = 1;
    register long long v;

    for(register EDGE *e = head[u]; e; e = e->ne){
        if(visit[v = e->to]) continue;
        fa[v] = u;
        dfs(v);
        siz[u] += siz[v];

        if(siz[fat[u]] < siz[v]) fat[u] = v;
    }

    return ;
}

void dfs(long long u, long long tp){
    static long long cnt = 0;
    register long long v;
    id[dfn[u] = ++cnt] = u;
    top[u] = tp;

    if(!fat[u]) return ;
    dfs(fat[u], tp);
    
    for(register EDGE *e = head[u]; e; e = e->ne){
        if(dfn[v = e->to]) continue;
        dfs(v, v);
    }

    return ;
}

NODE* Build(long long l, long long r){
    register NODE *p = new NODE();

    if(l ^ r){
        register long long mid = (l + r) >> 1;
        p->ls = Build(l, mid);
        p->rs = Build(mid + 1, r);
        p->sum = p->ls->sum + p->rs->sum;
    } else p->sum = val[id[l]];

    return p;
}

void update(NODE *node, long long l, long long r, long long k, long long L, long long R){
    if(l == L && r == R) node->tag += k;
    else{
        node->sum += k * (r - l + 1);
        register long long mid = (L + R) >> 1;
        if(r <= mid) update(node->ls, l, r, k, L, mid);
        else if(mid < l) update(node->rs, l, r, k, mid + 1, R);
        else {
            update(node->ls, l, mid, k, L, mid);
            update(node->rs, mid + 1, r, k, mid + 1, R);
        }
    }

    return ;
}

long long Query(NODE *node, long long l, long long r, long long L, long long R){
    if(node->tag) {
        node->sum += (R - L + 1) * node->tag;
        if(L ^ R){
            node->ls->tag += node->tag;
            node->rs->tag += node->tag;
        }
        node->tag = 0;
    }

    if(l == L && r == R) return node->sum;
    register long long mid = (L + R) >> 1;
    if(r <= mid) return Query(node->ls, l, r, L, mid);
    if(mid < l) return Query(node->rs, l, r, mid + 1, R);
    return Query(node->ls, l, mid, L, mid) + Query(node->rs, mid + 1, r, mid + 1, R);
}