记录编号	160468	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	2.099 s
提交时间	2015-04-27 18:11:36	内存使用	7.75 MiB

/*****************************************************************************/
/******************************Designed By Asm.Def****************************/
/*****************************************************************************/
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <ctime>
#define FREAD
#ifdef FREAD
#define FREADLENTH 5000000
char *fread_ptr = (char*)malloc(FREADLENTH);
#define getc() (*(fread_ptr++))
#else
#define getc() getchar()
#endif
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) )
using namespace std;
template<class T>inline void getd(T &x){
	int ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')neg = true, ch = getc();
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/*******************************************************************************/
const int maxn = 100005;
typedef long long LL;
#include <vector>
vector<int> adj[maxn];

int N, val[maxn], Begin[maxn], End[maxn], dep[maxn];

struct SegT{
	int L, R, mid;
	LL Sum, tg;
	SegT *ls, *rs;
	SegT(int l, int r):L(l), R(r), mid((l+r)>>1){
		Sum = tg = 0;
		if(l == mid){
			ls = rs = NULL;
			return;
		}
		ls = new SegT(l, mid);rs = new SegT(mid, r);
	}
	inline void push(){Sum += tg * (R - L);if(ls)ls->tg += tg, rs->tg += tg;tg = 0;}
	void Add(int l, int r, LL d){
		if(l == L && r == R){
			tg += d;push();
			return;
		}
		push();
		if(r <= mid)ls->Add(l, r, d);
		else if(l >= mid)rs->Add(l, r, d);
		else ls->Add(l, mid, d), rs->Add(mid, r, d);
		Sum = ls->Sum + rs->Sum;
	}
	LL Query(int i){
		if(tg)push();
		if(L == mid)return Sum;
		if(i < mid)return ls->Query(i);
		if(i >= mid)return rs->Query(i);
	}
}*R1, *R2;
	
void dfs(int cur, int p){
	static int Iter = 0;
	Begin[cur] = Iter++;
	vector<int>::iterator it;
	for(it = adj[cur].begin();it != adj[cur].end();++it)if(*it != p){
		dep[*it] = dep[cur] + 1;
		dfs(*it, cur);
	}
	End[cur] = Iter;
}

inline void init(){
	int i, a, b;
	for(i = 1;i <= N;++i)getd(val[i]);
	for(i = 1;i < N;++i){
		getd(a), getd(b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, 0);
	R1 = new SegT(0, N);R2 = new SegT(0, N);
	for(i = 1;i <= N;++i)R1->Add(Begin[i], End[i], val[i]);
}

inline void opt1(){
	int x, d;getd(x), getd(d);
	R1->Add(Begin[x], End[x], d);
}

inline void opt2(){
	int x, d;getd(x), getd(d);
	R1->Add(Begin[x], End[x], (LL)(1 - dep[x]) * d);
	R2->Add(Begin[x], End[x], d);
}

inline void query(){
	int x;getd(x);
	printf("%lld\n", R1->Query(Begin[x]) + R2->Query(Begin[x]) * dep[x]);
}

int main(){

#ifndef DEBUG
	SetFile(haoi2015_t2);
#else
	freopen("test.txt", "r", stdin);
#endif
#ifdef FREAD
	fread(fread_ptr, 1, FREADLENTH, stdin);
#endif
	int M, opt;getd(N), getd(M);
	init();
	while(M--){
		getd(opt);
		if(opt == 1)opt1();
		else if(opt == 2)opt2();
		else query();
	}

#ifdef DEBUG
	printf("\n%.3lf sec\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}